[Python] 백준 1270. 전쟁 - 땅따먹기 +) defaultdict 정리

문제

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

드디어 전쟁은 전면전이 시작되었고, 서로 땅을 따먹기 시작했다.

현재 여러 지역은 한창 전쟁이 벌어지고 있는 상황인데, 어느 지역은 거의 전쟁이 마무리 단계로 가고 있다.

하지만 당신은 군대를 보낼 때 적군을 혼란시키기 위해서 우리 나라의 군대라는걸 표시하지 않고, 군대의 번호로 표시했다.

어느 땅에서 한 번호의 군대의 병사가 절반을 초과한다면 그 땅은 그 번호의 군대의 지배하에 놓이게 된다.

이때, 각 땅들을 지배한 군대의 번호를 출력하여라. 만약, 아직 전쟁이 한창중인 땅이라면 “SYJKGW”을 쌍 따옴표 없이 출력한다.

입력

첫째 줄에는 땅의 개수 n(n<=200)이 주어진다. 그리고 두 번째 줄에서 n+1번째 줄에는 제일 처음에 숫자 Ti(i번째 땅의 병사수, Ti<=100,000)와, Ti개의 숫자 (각각 병사의 군대 번호)가 주어진다. i번째 땅의 j번째 병사 번호 Nij가 주어진다. ( | Nij | <= 2^31 )

출력

첫째 줄에는 각각의 땅의 상태를 순서대로 출력한다. 만약 땅이 지배가 되어있다면 그 지배한 병사의 번호를 출력하고, 아니라면 “SYJKGW”을 쌍 따옴표 없이 출력한다.

---

풀이

이 문제는 파이썬으로 풀게 된다면.. defaultdict를 사용하면 금방 풀 수 있다. 사실 나는 쓸 줄 몰랐었기 때문에...(제대로) 이번 기회에 정리하면서 확실하게 이해를 해보고자 한다.

 

일단 코드부터 풀이하자면...

import sys
from collections import defaultdict
input = sys.stdin.readline

n=int(input().strip())
for _ in range(n):
    data = list(map(int, input().split()))
    t = data[0]
    s = data[1:]

    count = defaultdict(int)
    for i in s:
        count[i] += 1

    h = t//2
    found = False
    for i in count:
        if count[i] > h:
            print(i)
            found = True
            break
    if not found:
        print("SYJKGW")

 

이렇다! 값을 입력 받고 defaultdict를 이용해서 count[i]에다가 횟수를 저장한 다음에 길이 절반 보다 큰 count[i]가 있으면 found를 True로 바꿔주고 어떤 땅이 이겼는지 출력. 찾지 못하면 "SYJKGM"을 출력하면 된다. 근데 아마 이 코드... 다른 분 코드를 참고 했던 것 같은데...못찾겠다...

 

사실상 코드 자체는 defaultdict을 알면 이해가 되는 구조이므로, 추가적인 설명은 넘어가고...

 

시간복잡도

defaultdict을 알기 전에! 시간복잡도부터 생각해보면... O(n*t)일 것 같다. (테스트케이스 수*병사 수)

dict 쓸 줄 ... 잘 몰라서 배열로 해보려다가 시간초과 출력초과.. 와장창..ㅜㅜ

---

defaultdict

키가 존재하지 않아도 기본값을 자동으로 생성해주는 딕셔너리. 딕셔너리와 거의 동일하게 작동하지만, 좀 더 편리하게 사용할 수 있는 것 같다.

#import 해오기
from collections import defaultdict

#선언해주기
count = defaultdict(int)

 

위 문제에서 이 딕셔너리 사용 방법을 보면 어떻게 사용할지 좀 더 쉽게 이해할 수 있다. 

for i in s:
    count[i] += 1

print(count, count[1])

 

이렇게 print를 찍어보면...

이런 식으로 나온다. 그러니까 i가 key값 역할을 하고 뒤에 횟수가 추가되고 count[i]를 하게 되면 해당하는 key값의 값을 출력해주는 구조. 

 

key값을 미리 만들어둘 필요없이 그때그때 필요한 key값을 추가해서 만들 수 있게 해주는 좋은 자료구조(확장 구현체)이다.