[BOJ] 듣보잡

---

코드

import sys
input = sys.stdin.readline

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

arr = list()
for _ in range(N+M):
    arr.append(input())

arr = sorted(arr) # 사전순 정렬

ans = 0        # 듣보잡 개수
dup = list()    # 듣보잡 리스트

for i in range(1, len(arr)):
    if arr[i] == arr[i-1]:    # 이전단어와 같은단어 찾기
        ans += 1
        dup.append(arr[i])
        i += 2    # 같은것이 2개까지만 있으므로 바로 다음단어는 건너뜀

# 정답출력
print(ans)
for w in dup:
    print(w, end='')

결과

풀이 방법

• 입력받는 단어의 개수가 최대 100만개이므로 단어 하나하나에 대해 전체 단어 중에서 중복여부를 일일이 찾을 수는 없다
• 먼저 N, M 단어를 모두 하나의 리스트에 저장한 다음 sorted() 함수를 사용하여 O(NlogN) 정도의 시간복잡도로 정렬하면 같은 단어 2개는 서로 붙어 있게 된다.
• 순차탐색(O(N))하면서 이전단어와 같은 단어를 찾으면 연산횟수가 1000만(대략 0.1초)인 선에서 문제를 해결할 수 있다고 판단했고 실제로 그 정도 시간이 소요됐다.

---