[백준/Python] 1764번 듣보잡 문제

■ 1764번 듣보잡 문제

 

출처: 백준 1764번 듣보잡 문제

 

■ 코드 풀이 #1: 통과(4028ms)

 

처음 문제를 봤을 때 두 가지 생각을 했습니다. 우선 첫 번째는 반복 횟수가 많으니 가급적이면 속도면에서 유리한 딕셔너리나 set을 활용해야겠다고 생각했습니다. 두 번째는 교집합을 표현할 수 있는 로직을 boolean을 활용하면 어떨까,라고 생각했습니다.

우선 먼저 그나마 편한 딕셔너리를 활용했고요. 듣도 못한 사람의 명단에 먼저 '이름 : False'로 딕셔너리에 저장합니다. 그리고 보도 못한 사람의 명단을 받으면서 기존에 이름이 없다면 당연히 교집합이 아니므로 다음 반복문으로 넘어(continue) 갑니다. 기존에 이름이 있다면 False를 True로 바꿔줍니다. 그럼 결과적으로 교집합인 사람들은 Value가 True로 남게 됩니다.

N, M = map(int, input().split())

no_see_listen = dict()
count = 0 
for _ in range(N):
    name = input()
    no_see_listen[name] = False
    
for _ in range(M):
    name = input()
    try:
        if no_see_listen[name] == False:
            no_see_listen[name] = True
            count +=1
    except KeyError:
        continue

print(count)
for key, value in sorted(no_see_listen.items()):
    if value == True:
        print(key)

 

 

■ 코드 풀이 #2: 3640ms

 

두 번째는 set을 활용한 코드입니다. set도 딕셔너리와 마찬가지로 hash table 구조를 활용하기 때문에 속도가 빠른 편인데요. 위의 코드와 속도는 비슷하지만 코드가 간결하고 직관적으로 이해할 수 있어서 더 좋은 코드인 것 같습니다.

N , M = map(int,input().split())

no_see = set()
no_listen = set()

for _ in range(N):
    no_see.add(input())
for _ in range(M):
    no_listen.add(input())

no_see_listen = sorted(list(no_see & no_listen))
print(len(no_see_listen))

for i in no_see_listen:
    print(i)