[백준 알고리즘] 14425번: 문자열 집합 (파이썬 / Python)

문제

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

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

입력

 

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

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

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

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

출력

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

예제 입력

5 11
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
codeplus
codeminus
startlink
starlink
sundaycoding
codingsh
codinghs
sondaycoding
startrink
icerink

예제 출력

4

---

문제 접근

리스트로 구현할 시 시간초과가 될 것으로 예상되었다.

s = 'abcdef'
print('bc' in s)

#출력결과 : True

처음에는 위와 같은 속성을 활용하여, 검사해야 하는 모든 문자를 다 더해 하나의 문자열로 만들고 검사하려 했다.

그러나 그러면 'baekjoononlinejudge'라는 문자로 인해 'baekjoon'이 카운트되는 문제가 있었고,

예제에는 없었지만 문자들이 합쳐지면서 만들어진 단어가 의도치 않게 카운트될수도 있는 큰 문제가 있었다.

---

따라서 집합을 만들어서 집합에 문자들을 추가하는 방향으로 잡았다.

s = set()
for _ in range(n):
    s.add(sys.stdin.readline().strip())

위와 같이 구현할 수 있는데, 파이썬은 set() 내장함수가 잘 구현되어 있기에 가져다 쓰면 된다.

* set()은 hash로 구현되어 있어, index가 존재하는 list와는 다르게 in 작업을 할 때 시간복잡도가 평균 O(1)이다.

 

정답 코드

import sys

def test():
    n, m = map(int, sys.stdin.readline().split())
    s = set()
    for _ in range(n):
        s.add(sys.stdin.readline().strip())

    count = 0
    for _ in range(m):
        voca = sys.stdin.readline().strip()
        if voca in s:
            count += 1

    print(count)

test()

1. 문자들을 입력받아 s집합에 넣는다.

2. 검사해야할 문자를 입력받음과 동시에 s집합에 있는지 검사하고 있다면 카운트를 해준다.

---

14425번: 문자열 집합