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

문제 출처 : www.acmicpc.net/problem/1764

1764번: 듣보잡

내 풀이(시간초과)

import sys

input = sys.stdin.readline

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

arr1 = dict()
answer = []
for i in range(n):
    x = input()
    if len(x) not in arr1:
        arr1[len(x)] = list()        
    arr1[len(x)].append(x)
for i in range(m):
    y = input()
    if len(y) in arr1:
        if y in arr1[len(y)]:
            answer.append(y)

answer.sort()
print(len(answer))
print(''.join(answer), end = '')

내 풀이 1 (성공)

import sys

input = sys.stdin.readline

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

arr1 = dict()
answer = []
for i in range(n):
    x = input()
    if x not in arr1:
        arr1[x] = i

for i in range(m):
    y = input()
    if y in arr1:
        answer.append(y)
        
answer.sort()
print(len(answer))
print(''.join(answer), end = '')

내 풀이 2 (성공)

import sys

input = sys.stdin.readline

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

arr1 = []
arr2 = []
for i in range(n):
    x = input()
    arr1.append(x)
for i in range(m):
    y = input()
    arr2.append(y)

answer = list(set(arr1) & set(arr2))
answer.sort()
print(len(answer))
print(''.join(answer), end = '')

설명 

시간초과 코드

n, m 각각의 그룹 중 하나를 길이별로 나눠서 딕셔너리에 저장한 후에 

나머지 한쪽이 길이를 가지고 해당 아이템 안에 있는 벨류를 탐색하도록 구현했다.

이럴 경우 특정 길이의 이름이 많이 존재할 경우 시간복잡도가 커져서 시간초과가 나는 것을 생각하지 못했다.

성공 1 코드

때문에 생각을 바꿨다.

기본적으로 딕셔너리함수에서 'in'연산자의 시간복잡도가 O(1)이라는 부분을 기준으로 생각하기로 했다.

각 문자열 자체를 아이템으로 넣고 내부 벨류는 그냥 순회하면서 i를 넣어주도록 했다.

그 다음 나머지 집단에서 'in'을 통해 해당 아이템이 딕셔너리에 존재하는지 확인 후에 

존재할 경우에만 answer에 넣어주도록 했다.

성공 2 코드

사실 가장 간단히 떠올릴 수 있는 가장 손쉬운 방법이라고 생각했다.

n, m 각 그룹을 set으로 풀어준 뒤에 '&'연산자를 통해 교집합 부분만 빼내어 새로 list를 만들고

출력해내면 되는 문제였다.

결론

'in' 연산자의 시간 복잡도

list, tuple

• 평균 : O(n)

set, dictionary

• 평균 : O(1)