[백준] 1270 - 전쟁 - 땅따먹기 (python)

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

4
10 1 2 3 1 2 3 1 2 3 1
5 1 1 1 2 2
6 10 10 2 10 10 2
6 1 1 1 2 2 2 

예제 출력 1 복사

SYJKGW
1
10
SYJKGW

풀이

from collections import Counter
from collections import deque
import sys
input=sys.stdin.readline
for i in range(int(input())):
    arr = deque(map(int, input().split()))
    length=arr.popleft()
    total=Counter(arr)
    total_values=sorted(total.items(), key=lambda x: x[1], reverse=True)
    if total_values[0][1] * 2 > length :
        print(total_values[0][0])
    else:
        print('SYJKGW')

하나의 리스트에 대하여 과반수 이상만 체크 하면 되는 문제인데,

list.count(1)과 같이 하나하나 개수를 세서 저장한다면 시간초과 날 것이다.

그렇기에 Counter는 요소들의 출현 횟수를 딕셔너리에 저장하므로 사용하였고

total_values=sorted(total.items(), key=lambda x: x[1], reverse=True)

이부분이 핵심일 것 같다. 

그냥 sorted(total)일 경우엔 key값으로 저장되지만 lambda를 이용해 value로도 정렬 할 수 있었음.

그래서 정렬후 제일 큰 value를 가진 하나만 체크 해서 과반수면 그에 해당하는 key를 출력하는 식으로 풀었음.

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

1270번: 전쟁 - 땅따먹기