[실버 IV] 1764번. 듣보잡

 문제 

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 사용 언어 

Python3

 풀이 과정 

IDE에서는 예시 정답이 출력되는 것을 확인했으나 백준에서는 (역시) 시간 초과가 떴다. 그래도 이제는 코드를 짜면서 이게 시간 초과가 날 것 같은 코드라는 느낌이 왔달까..? 이걸발전한거라고 할 수 있나ㅎㅎ;

import sys

N, M = map(int, input().split())
names = []
result = []
count = 0
for _ in range(N+M):
    name = sys.stdin.readline().strip()
    if name in names:
        result.append(name)
        count += 1
    else:
        names.append(name)

print(count)
print(*sorted(result), sep='\n')

배열에 몽땅 집어넣고 비교하는 방식은 시간 초과가 났으니 뭘 어떻게 바꾸나 하다가 집합으로 바꿔서 교집합을 사용했는데 엄청 빨리 채점되더니 뜬 맞았습니다!!

append나 add나 시간복잡도는 O(1)로 같은데 리스트에 이름이 있는지 확인하는 in연산자가 O(N)의 시간복잡도로 for문 안에 있어서 차이가 난 것 같다. 참고로 집합 연산자의 합집합, 교집합, 차집합, 여집합은 모두 O(len(s)+len(t))의 시간복잡도를 가진다고 한다. 또 list.sort()와 sorted(list) 내장함수는 병합정렬과 삽입정렬을 조합해 O(n log n)의 시간복잡도를 가진다.

 제출 답안 

import sys

N, M = map(int, input().split())
N_names = set()
M_names = set()
for _ in range(N):
    N_names.add(sys.stdin.readline().strip())
for _ in range(M):
    M_names.add(sys.stdin.readline().strip())

intersection = list(N_names & M_names) # 교집합
print(len(intersection))
print(*sorted(intersection), sep='\n')

 공부한 내용 

리스트 자료형과 메서드의 시간 복잡도

집합(set) 자료형과 메소드의 시간 복잡도

딕셔너리(Dictionary) 자료형과 메소드의 시간 복잡도

자료형에 따른 시간 복잡도 비교

메서드들의 시간 복잡도가 다르기 때문에 필요에 따라서 어떤 자료형을 사용하는 것이 좋은지 생각하면 더욱 좋은 알고리즘으로 파이썬 코드를 작성하실 수 있을 것이다.

List와 Tuple 자료형은 삽입, 제거, 탐색, 포함 여부 확인 모두 O(n)에 해당하는 시간 복잡도를 가지고 있다.

하나 하나 순회하기 때문에 데이터의 크기만큼 시간복잡도를 갖게 되는 것이다.

반면 Set과 Dictionary는 삽입, 제거, 탐색, 포함여부확인 연산에 O(1)의 시간 복잡도를 가지고 있다.
내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생한다.

따라서 탐색과 확인이 주로 필요한 연산이라면 Set이나 Dictionary를 사용하는 것이 좋고 순서와 index에 따른 접근이 필요하다면 List 자료형을 사용하는 것이 좋을 것이다.

 

출처: https://chancoding.tistory.com/43  | https://twpower.github.io/120-python-in-operator-time-complexity

 다른 사람 답안 

set 자료형 말고 dictionary 자료형도 탐색에 O(1) 시간복잡도가 걸리기 때문에 이를 활용한 코드를 찾아볼 수 있었다.

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)

출처: https://trey-de.tistory.com/9

 

키-값을 추가하는건 똑같지만 값이 2인 개수를 확인하는 과정이 추가돼서 시간복잡도가 조금은 더 걸리지 않을까 했는데 예상대로였다. 하지만 딕셔너리를 활용한 방법으로도 리스트를 활용하는 것과는 차원이 다르게 시간이 줄어든다는 점..! 기억해둬야겠다.