백준 알고리즘 파이썬(Python) 1764번 듣보잡

---

 

 

deque를 이용한 풀이

#deque를 썼으나 시간초과

import collections
n, m = map(int, input().split())

d = collections.deque()
b = collections.deque()
db = collections.deque()

for i in range(n+m):
    b.append(input())

for i in range(n):
    d.append(b.popleft())
    
for i in range(len(d)):
    if d[i] in b:
        db.append(d[i])
        
db = sorted(db)
print(len(db))
for i in range(len(db)):
    print(db[i])

우선 주어진 N과 M이 500,000 이하의 자연수로 컸기 때문에 

list로는 시간 초과가 날 것 같아서 deque를 사용했다.

 

1. 처음 b(보잡)에 모든 단어를 넣어놓고 처음 N개를 pop 해줘 d(듣잡)에 넣어줬다.
2. 이러면 듣잡과 보잡이 나누어지고 그중 공통된 것을 탐색해 db(듣보잡)에 넣어줬다.
3. 그리고 db를 정렬한 후 db의 길이와 db의 원소를 각각 출력해주었다.

하지만 결과는 시간초과

 

 

 

---

 

 

 

set을 이용한 풀이

n, m = map(int, input().split())

d = set()
b = set()

for i in range(n):
    d.add(input().rstrip())

for j in range(m):
    b.add(input().rstrip())
    
db = sorted(list(d & b))

for i in db:
    print(i)

결국 검색을 통해 set(집합)을 이용해 풀어야 한다는 것을 알았다.

알고리즘 원리는 위의 문제와 동일하다.

 

 

 

deque는 조회에 O(N)의 시간이 걸리지만 set은 조회에 O(1)이 걸리므로 set을 이용해야 하는 문제였다.