백준 1764번: 듣보잡 - 파이썬

백준 1764번: 듣보잡 (www.acmicpc.net/problem/1764)

 

💡접근

• 제한 시간 : 2초
• 듣도 못한 사람 리스트, 보도 못한 사람 리스트에서 중복 원소를 찾아야하는 문제이다.
• 두개의 리스트를 만들어 이중 for loop으로 모든 원소를 비교할 경우, 최악의 경우 50만x50만 = 2500억번의 연산을 해야하므로 시간초과가 날 수 있다.
• 따라서, 탐색하는 시간이 O(1)걸리는 python dictionary를 사용해서 풀어보면 어떨까?
• 먼저, 듣도 보도 못한 종류의 관계없이, 이름을 key값으로 가져가고, key가 처음 생기는 경우라면 1을 넣어준다.
• → 삽입에 총 O(n) 시간복잡도가 소요됨
• key값이 앞에서 만들어져있는 상태에서 또 같은 key값이 입력값으로 들어온다면, 해당 key값의 value에 +1을 해준다.
• → 같은 key값인지 확인하는데에는 O(1) 시간복잡도가 소요됨
• value가 2인 모든 key값을 프린트해준다.
• 결과를 프린트할때는 list.sort() 또는 sorted(list)를 사용하면 좋을 것 같다
• → 내장함수의 시간복잡도 O(n log n) → 내부적으로 병합정렬과 삽입정렬을 조합해서 만들었다고함.

 

💡배운점 및 오답원인

• 다른사람들은 Python의 set과 set의 교집합 & 연산을 이용해서 풀고, 시간초과는 안났다고 한다.
• ⚠️ set끼리 % 연산하는것은 내부적으로 어떻게 동작하는지는 찾아보기 (&연산은 bitwise operation이다.)

 

💡풀이 코드

import sys

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

dic = {}
for i in range(n+m):  # O(n)
    name = sys.stdin.readline().strip()
    # dictionary에 key값이 처음 들어가는 경우
    if name not in dic:  # O(1)
        dic[name] = 1
    # dictionary에 key값이 이미 들어가 있는 경우
    else:
        dic[name] = dic[name]+1  # O(1)

answer = []
for k, v in dic.items():  # O(n)
    if v == 2:
        answer.append(k)
print(len(answer))
print("\n".join(sorted(answer)))  # O(n)