[백준] 1764 - 듣보잡 Python

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

1764번: 듣보잡

(1) list 사용 - 시간초과

import sys

input = sys.stdin.readline

N, M = map(int, input().split(" "))
list1 = list()
list2 = list()

for i in range(N):
    list1.append(input().rstrip())
list1.sort()

for i in range(M):
    name = input().rstrip()
    if name in list1:
        list2.append(name)

list2.sort()
print(len(list2))
for name in list2:
    print(name)

첫번째 코드.. 사실 엄청 쉬운줄 알고 룰루랄라 list~~ sort~~사용해서 썼지만.. 시간초과에 걸렸다. N과 M이 500,000이하의 자연수라는 것을 고려하지 않고 작성했기 때문이다. list in을 쓰면 O(N **2)가 걸리는데.. 이를 무시하고 코드를 짠 결과이다. 그래서 딕셔너리로 수정하는 것으로 바꿨고, 딕셔너리는 in이 O(1)이 걸린다는 것을 활용했다.

 

(2) 정답코드 - 딕셔너리 사용

import sys

input = sys.stdin.readline

N, M = map(int, input().split(" "))
arr1 = dict()
list2 = list()

for i in range(N):
    name = input().rstrip()
    arr1[name] = 0

for i in range(M):
    name = input().rstrip()
    if name in arr1:
        list2.append(name)

list2.sort()
print(len(list2))
for name in list2:
    print(name)

 

 

 

---

https://github.com/sumini0516

sumini0516 - Overview