[백준] No.1764_듣보잡 01

1764번: 듣보잡

문제 해석)
숫자 N과 M을 받아들인다. N만큼의 무작위 입력을 받고, M만큼의 무작위 입력을 받는다.

N과 M에서 중복되는 입력을 개수와 사전순으로 출력한다.

 

import sys
input = sys.stdin.readline

not_see, not_listen = map(int, input().split())
not_see_lst = []
not_at_all = []

for _ in range(not_see):
    not_see_lst.append(input().rstrip())
    not_see_lst.sort()
    
for _ in range(not_listen):
    not_listen_word = input().rstrip()
    if not_listen_word in not_see_lst:
        not_at_all.append(not_listen_word)
        
not_at_all.sort()
print(len(not_at_all))

for _ in not_at_all:
    print(_, end=" ")

맨 처음엔 문제를 보자마자 생각나는 대로 작성한 코드이다.

출력 형식은 우선 맞추지는 않고 제대로 계산이 되나만 확인을 해보았다.

 

처음에 input()으로 받아들이고 테스트를 진행했더니 \n 개행문자도 같이 출력을 했다.

그래서 rstrip()으로 개행 문자를 지우고 리스트에 추가했다.

for문에 if문이 들어가 있어서 최소 O(n^2)의 시간복잡도일 텐데...아마 시간 초과가 뜨리라 예상

그리고 정확하게 시간 초과

 

숫자 카드 1과 숫자 카드 2처럼 이분 탐색을 써야 하나?

이분 탐색을 쓴다면 맨 처음 알파벳을 기준으로 탐색해야 하나?

입력 받은 값을 사전으로 만들어서 비교해야 하나?

아이디어만 얻기 위해 찾아보던 중 충격적인 코드를 봤다.

 

이렇게까지 짧을 수 있다고??

set 자료형을 사용한 게 중복 입력을 없애려고 사용한 것 같다.

그런데 이미 전제 조건이 '중복이 없다'이니까 굳이 set을 써야 하나?라는 생각이 들었다.

 

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

a = []
for i in range(N):
    a.append(input())
    
b = []
for i in range(M):
    b.append(input())
    
result = sorted(list(a & b))

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

그래서 위와 같은 코드로 리스트만을 사용해서 코드를 바꿔보고, 테스트를 진행했다.

 

핵심은 "result = sorted(list(a & b))" 부분이었다.

& 연산은 리스트와 리스트는 할 수 없다? 그럼 set() 자료형에서는 지원을 한다는 건가?

 

그렇다.

set 자료형은 1. 중복을 허용하지 않는다. 2. 순서가 없다라는 특징과 함께 집합 연산이 가능하다.

교집합(&, intersection), 합집합(|, union), 차집합(-, difference)의 연산이 가능하다.

 

그리고 시간이 3784ms가 걸린 코드는 input()을 사용하여 입력을 받았고,

124ms가 걸린 코드는 sys.stdin.readline()을 사용하여 입력을 받은 차이이다.

입력이 커지게 되면 생각보다 많은 시간 차이가 나니 이것도 고려하자.

 

위와 같은 기능의 유무도 중요하지만, 결국에는 시간을 줄이기 위함이다.

이와 관련하여 list, set, dict에 관한 시간 복잡도 Big-O에 대한 링크를 자주 읽어보자.

List, Set, Dict 자료형에 따른 시간 복잡도(Big-O)

 

그리고 이런 식으로 깨닫는 것도 좋지만, 내 생각을 키우기 위해서는

조금 더 늦게 검색을 해야 할 것 같다는 생각이 들었다.