TIL 23-06-11 백준-듣보잡

1.백준-듣보잡

 문제점

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

 시도해 본 것들

# 듣지 못한 수 N
# 보지 못한 수 M
# 듣지도 못하고 보지도 못하면 출력

 

dict get사용하기

N, M = map(int, input().split())
persons = {}
for _ in range(N + M):
    name = input()
    persons[name] = persons.get(name, 0) + 1
unknown_list = [i[0] for i in sorted(persons.items()) if i[1] == 2]
print(len(unknown_list))
print("\n".join(unknown_list))

N과 M이 구분되어 있지만, 중복해서 이름을 출력하지 않으므로 이름이 2번 나온 경우가 듣지도 보지도 못한 경우이므로

for문을 N+M으로 실행 

get을 사용해서 name이 있다면 value를, 없다면 0으로 설정하고 +1하기 

사전순으로 정렬하며 value가 2면 key를 저장한다

 

dict if문 사용하기 

    if name not in persons:
        persons[name] = 1
    else:
        persons[name] += 1

위의 방식으로 통과는 했으나 시간이 5000ms가 나오는 상황발생

가독성은 get이 좋다고 생각하지만 연산 속도가 if문이 빨랐던 경험이 있어서 if문으로 교체

3800ms 소요

 

set()자료형 사용

N, M = map(int, input().split())
persons_set = set()
unknown_set = set()
for _ in range(N + M):
    name = input()
    if name not in persons_set:
        persons_set.add(name)
    else:
        unknown_set.add(name)
print(len(unknown_set))
print("\n".join(sorted(unknown_set)))

set()을 사용했지만 마찬가지로 3700ms 정도 소요

key에 접근하는 dict나 해시 테이블로 접근하는 set을 사용 했는데 이만큼 시간이 걸리는 것은 자료형의 문제가 아님을 깨달음

 

 해결 방법

sys.stdin.readline()사용

set()

from sys import stdin
N, M = map(int, stdin.readline().split())
persons_set = set()
unknown_set = set()
for _ in range(N + M):
    name = stdin.readline().strip()
    if name not in persons_set:
        persons_set.add(name)
    else:
        unknown_set.add(name)
print(len(unknown_set))
print("\n".join(sorted(unknown_set)))

 

dict()

from sys import stdin
N, M = map(int, stdin.readline().split())
persons = {}
for _ in range(N + M):
    name = stdin.readline().strip()
    persons[name] = persons.get(name, 0) + 1
unknown_list = [i[0] for i in sorted(persons.items()) if i[1] == 2]
print(len(unknown_list))
print("\n".join(unknown_list))

readline()을 사용하며 시간을 확인하는 과정에서 if문을 사용한 것 보다 get을 사용한 코드가 더 빨랐다. 

 

 알게 된 점

보통 split()이 필요없는 입력의 경우 input()을 주로 사용해서 readline()의 경우 \n을 포함하여 출력된다는 점을 이번에 알게됐다. 

if와 get중에서 사용하고 싶은 방법을 사용해도 성능적으로 크게 관련이 없는 것 같다.