[Baekjoon] 1764번 : 듣보잡 (Python, 문자열, 정렬, set, 해시)

[Baekjoon] 1764번 : 듣보잡 (Python, 문자열, 정렬, set, 해시)

 

목차

 

 

 

 

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

1764번: 듣보잡

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 -  코드 길이 215B

 

입력을 받고 첫 d에서 정렬을 진행한 다음 b에도 존재하는지 확인하는 테스트를 거친다.

다만 이 경우 시간 초과가 난다.

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
d = [input().rstrip() for _ in range(n)]
b = [input().rstrip() for _ in range(m)]
d.sort()
l = []
cnt = 0
for i in d:
    if i in b:
        cnt += 1
        l.append(i)

 

방법 2 - 메모리 37756KB / 시간 112ms / 코드 길이 285B

 

해시를 이용한 방법으로 첫 n개에 대한 입력을 c dict에 저장한다. 이후 m개에 대한 값을 받을 때마다 단어가 c에 존재하는지 확인하여 작업을 처리한다.

 

유의) 이때 저장한 list의 정렬을 진행한 다음 출력을 진행해야 사전순으로 출력한다.

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
c = {}
l = []
cnt = 0

for i in range(n):
    c[input().rstrip()] = 1

for j in range(m):
    t = input().rstrip()
    if t in c:
        cnt += 1
        l.append(t)

l.sort()
print(cnt)
print('\n'.join(l))

 

방법 3 - 메모리 42108KB / 시간 128ms / 코드 길이 251B

 

set의 교집합으로 처리하는 방법이 있다.

 

set의 intersection 혹은 &를 통해 set 간의 중복되는 교집합 원소를 구할 수 있다.

그러나 많은 메모리를 소모한다.

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
a,b = set(), set()

for i in range(n):
    a.add(input().rstrip())

for i in range(m):
    b.add(input().rstrip())

res = sorted(list(a & b))

print(len(res))
print('\n'.join(res))

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
d = [input().rstrip() for _ in range(n)]
b = [input().rstrip() for _ in range(m)]

res = sorted(list(set(d) & set(b)))

print(len(res))
print('\n'.join(res))