사용자 도구

사이트 도구


ps:problems:boj:14425

문자열 집합

ps
링크acmicpc.net/…
출처BOJ
문제 번호14425
문제명문자열 집합
레벨실버 3
분류

기초

시간복잡도O((n+m)l)
인풋사이즈n<=10,000, m<=10,000, l<=500
사용한 언어Python
제출기록34512KB / 140ms
최고기록132ms
해결날짜2020/12/28

풀이

  • 트라이 (Trie)로 태그된 문제들을 찾다가 풀게 된 문제이지만, 사실 이 문제에 트라이는 필요없다.
    • 단순히 집합에서 원소의 유무를 찾는 작업에는 trie나 set이나 시간복잡도가 동일하다. N개의 문자열로 구성된 set생성에 O(N*l), M개의 문자열을 검색하는 데에 O(M*l) 이다.
  • input()이 아닌 sys.stdin.readline()을 써서 입력받을 때에는, 원래 rstrip()를 써서 개행문자를 제거해 주는 것이 정석이지만, 이 경우처럼 두 문자열의 일치 여부만 비교하면 될 때에는 둘 다 개행문자가 붙어있더라도 비교 결과는 똑같으므로, rstrip()를 생략했다

코드

"""Solution code for "BOJ 14425. 문자열 집합".

- Problem link: https://www.acmicpc.net/problem/14425
- Solution link: http://www.teferi.net/ps/problems/boj/14425
"""


import sys


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    s = {sys.stdin.readline() for _ in range(n)}
    count = sum(sys.stdin.readline() in s for _ in range(m))
    print(count)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
E K B L N
 
ps/problems/boj/14425.txt · 마지막으로 수정됨: 2020/12/28 14:22 저자 teferi