듣보잡(백준 1764번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가? ✓

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

---

난이도 체감

1. 최상

2. 상

3. 중

4. 하✓

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

나의 풀이(시간 초과)

import sys
N,M=map(int,input().split())
D_M=[]
for _ in range(N):
    D_name=sys.stdin.readline().strip()
    D_M.append(D_name)
DB_count=0
answer=[]
for _ in range(M):
    B_name=sys.stdin.readline().strip()
    if B_name in D_M:
        answer.append(B_name)
        DB_count+=1
answer.sort()  
print(DB_count)
for ans in answer:
    print(ans)

• 위 방법대로 했을 때, 시간 초과가 발생하였다. 예상한 원인은, if B_name in D_M: 이 부분이다.
• 따라서 dictionary로 다시 한번 풀어보았다.

나의 풀이(정답)

import sys
N,M=map(int,input().split())
D_M=dict()
for _ in range(N):
    D_name=sys.stdin.readline().strip()
    D_M[D_name]=0
DB_count=0
answer=[]
for _ in range(M):
    B_name=sys.stdin.readline().strip()
    try:
        D_M[B_name]+=1
        DB_count+=1
        answer.append(B_name)
    except:
        continue
answer.sort()
print(DB_count)
for ans in answer:
    print(ans)

• 만약 dictionary에 해당 키가 없으면 오류가 발생하기 때문에, 바로 겹치는 명단인지 아닌지 알 수 있다. dictionary는 HashTable형태로 되어있기 때문에, key값을 통해 찾는 것은 O(1)의 시간복잡도를 갖는다.

---

다른 사람 풀이(Set()이용)

n,m = map(int,input().split())
a=set()
b=set()
result =[]
for _ in range(n):
    a.add(input())
for _ in range(m):
    b.add(input())

for i in a :
    if i in b :
        result.append(i)
result.sort()
print(len(result))
for i in result :
    print(i)

출처: https://night-knight.tistory.com/entry/백준1764-듣보잡-python-파이썬

• 생각해보니 set()함수를 사용해도, 시간 초과 없이 문제를 풀 수 있다.
• in함수는 set함수를 사용하게 될때 해시테이블을 이용하므로 O(1)시간 복잡도를 갖는다.
• in함수 list에서 시간복잡도는 O(N)