[baekjoon] 백준 1764번(파이썬): 듣보잡

문제

1764번: 듣보잡

알고리즘

- Counter 클래스를 사용하여 이름의 수를 확인한다.

- 반복문을 통해 이름의 수가 2 이상이고 리스트에 없는 요소라면 리스트에 추가한다.

- 리스트를 오름차순으로 정렬 후 길이를 출력하고 반복문을 통해 이름을 출력한다.

코드

import sys
from collections import Counter # collections 모듈에 Counter 클래스 사용

n, m = map(int, sys.stdin.readline().split())
res = []
name = []
for i in range(n + m):
    name.append(str(sys.stdin.readline().strip("\n")))

temp = Counter(name) # 이름의 수를 확인

# 반복을 통해 중복되는 이름이 있는지 확인
for i in name:
    # 카운트가 2번 이상인 사람이고
    # 그 사람의 이름이 리스트의 없다면 리스트에 추가한다.
    if temp[i] >= 2 and i not in res:
        res.append(i)

# 오름차순으로 정렬한다.
res.sort()

print(len(res))
for i in res:
    print(i)

 

실패한 코드(시간초과)

import sys

n, m = map(int, sys.stdin.readline().split())
temp = []
res = []
for i in range(n + m):
    name = str(sys.stdin.readline().strip("\n"))
    if name not in temp:
        temp.append(name)
    else:
        res.append(name)

# print(temp)
print(len(res))
res.sort()
for i in res:
    print(i)

for문에서 시간 복잡도가 O(N) 인데 temp 리스트에 name을 계속해서 확인하면서 시간초과가 나는 것으로 보인다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법