[Python] 백준 14425번 - 문자열 집합

https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 자료구조
 - 문자열
 - 해시를 사용한 집합과 맵
 - 트리를 사용한 집합과 맵

 

문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

 

---

 

시간제한을 타이트하게 둔 문제이기 때문에 문자열을 비교하는 기능을 잘 사용할 줄 알아야 한다.

 

 

1. list() 사용

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
data = list()
for i in range(n):
    s = input().rstrip()
    data.append(s)
cnt = 0
for i in range(m):
    s = input().rstrip()
    if s in data:
        cnt += 1
print(cnt)

리스트에 담아서 하나하나 in을 사용해 비교하는 방식으로 풀었다.

정답은 맞았으나 3768ms의 적지 않은 시간이 소요되었다.

 

2. set() 사용

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
data = set()
for i in range(n):
    s = input().rstrip()
    data.add(s)
cnt = 0
for i in range(m):
    s = input().rstrip()
    if s in data:
        cnt += 1
print(cnt)

set을 사용하니 136ms로 시간이 굉장히 단축되었다.

 

둘의 코드는 거의 유사하다.

 

차이는 list를 사용하였나 set을 사용하였나의 차이뿐

 

관건은 둘이 in 과정의 탐색 차이인데

 

https://kyleyj.tistory.com/56

[Python] List와 Set에서의 in 연산자 성능 비교하기.

 

list에서 in 연산자의 시간 복잡도는 O(n)

set에서 in 연산자의 시간 복잡도는 O(1) (dict도 동일)

 

위의 차이로 인해 문제 푸는 시간에서 큰 차이가 발생하였다.