[BOJ] 14425 문자열 집합 (Python)

문제 내용

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

풀이 전략

Hash

⏰14분⏰

해쉬 자료구조를 이용해 쉽게 풀 수 있는 문제였다.
사실 set을 이용하든, dictionary를 이용하든 in 연산을 수행할 때 $O(1)$ 의 시간복잡도가 소요되므로 상관없다.

사실 index를 전부 단어로 때려박으면 시간복잡도가 더 단축될 테지만, 시간 측면에서 더 오래 걸리지만 뭔가 실제로 쓸법한 방법을 사용해 보았다. 앞 문자를 index로 구성해 실제 사전처럼 앞 문자가 같은 단어들을 값에 list 자료구조를 이용해 집어넣었다.

효율성 테스트 통과를 못 하면 index를 전부 단어로 때려박으려 했는데, 통과해서 그냥 이 코드로 제출했다.

n개의 자료를 dictionary에 집어넣는 첫 번째 루프에서 $O(n)$이 걸리고,
m개의 자료를 dictionary에서 in 연산을 수행하는 두 번째 루프에서 $O(m * n)$ 이 걸리므로,
총 시간복잡도는 $O(n * m)$ 으로, 문자열의 갯수가 조금만 많아져도 알고리즘을 이용할 수 없을 정도다.

만약, 단어를 전부 index로 때려박는 방법을 이용하면 linear time에 문제를 해결할 수 있다.

백준에서 답을 제출해 보면 두 방법이 걸리는 시간 차이가 상당히 많이 남을 알 수 있다.
(근데 이정도면 그냥 list를 이용해도 될 듯)

구현

앞 문자로 dictionary의 index로 구현한 코드

import sys

if __name__ == "__main__":
    input = sys.stdin.readline
    
    n, m = map(int, input().split())
    answer = 0
    s_dict = {}
    
    for _ in range(n):
        word = input()
        if (first:=word[0]) in s_dict:
            s_dict[first].append(word)
        else:
            s_dict[first] = [word]
    
    for _ in range(m):
        compare = input()
        if (pre:=compare[0]) in s_dict:
            if compare in s_dict[pre]:
                answer+=1
    
    print(answer)

전체 문자열을 dictionary의 index로 구현한 코드

import sys

if __name__ == "__main__":
    input = sys.stdin.readline

    n, m = map(int, input().split())
    answer = 0
    s_dict = {}

    for _ in range(n):
        word = input()
        s_dict[word] = None

    for _ in range(m):
        compare = input()
        if compare in s_dict:
            answer+=1

    print(answer)