[ 파이썬(python) ] 백준 10546 - 배부른 마라토너

📍 백준 10546 - 배부른 마라토너

백준 10546 - 배부른 마라토너

---

⚡️ 나의 풀이

저번에 풀었던 프로그래머스 - 완주하지 못한 선수 와 동일한 문제다. 참가자의 수가 100,000이기 때문에 기본적으로 list를 사용해서 풀면 시간 초과가 난다. 그래서 dict를 사용해서 풀었다.

 

1. 참가자를 저장할 dict와 완주 선수를 저장할 dict를 defaultdict로 선언한다. defaultdict를 선언하면 동일 선수가 나와도 +1을 할 수 있기때문에 유용하게 사용할 수 있다.
2. Counter 라이브러리로 참가자와 완주자의 Counter를 준다. 간단한 팁이지만 Counter끼리는 서로 빼거나 더할 수 있다.
3. 남은 값의 key를 출력한다.

 

이런방식은 정답 판정을 받을 수 있으나, 메모리와 실행시간이 오래 걸린다. 다른 좋은 방법이 있는지 찾아봤는데 다음과 같다.

 

1. 참가자를 defaultdict로 선언하고 한명씩 추가한다.
2. 완주자를 참가자의 값에서 빼준다.
3. 반복문을 사용하여 value가 1이상인 값만 출력한다.
4.  

이 방식으로 제출했더니 큰 차이는 아니지만 메모리와 실행시간이 소폭 줄었다.

 

 

# 나의 풀이
import sys
from collections import defaultdict, Counter
input = sys.stdin.readline

n = int(input())
participants = defaultdict(int)
finisher = defaultdict(int)

for _ in range(n):
    name = input()
    participants[name] += 1

for _ in range(n-1):
    name = input()
    finisher[name] -= 1

print(''.join((Counter(participants) - Counter(finisher)).keys()))

# 다른 사람의 풀이
import sys
from collections import defaultdict
input = sys.stdin.readline

n = int(input())
participants = defaultdict(int)

for _ in range(n):
    name = input().rstrip()
    participants[name] += 1

for _ in range(n-1):
    name = input().rstrip()
    participants[name] -= 1

for key, value in participants.items():
    if value >= 1:
        print(key)