[파이썬/백준 1270]전쟁 - 땅따먹기

3달 전에 계속 시간 초과가 나와서 잠시(포기한건 아님) 해결을 뒤로 미뤄놨던 문제다.

 

지금 다시 보니 예쁘게 생기긴 했지만, 효율성은 0인 코드였다.

오늘 푼 코드도 딕셔너리를 사용하면 시간이 좀 더 단축될 거 같긴 하지만.. 일단은 통과했다!

 

 

링크> www.acmicpc.net/problem/1270

1270번: 전쟁 - 땅따먹기

코드>

import sys

input = sys.stdin.readline

n = int(input())
for _ in range(n):
    land = list(map(int, input().split()))
    land.sort()

    left = right = 0
    answer = []
    while right < len(land):
        if land[left] == land[right]:
            right += 1
        else:
            answer.append((right-left, land[left]))
            left = right
    answer.append((right - left, land[left]))
    answer.sort()

    cnt, army = answer[-1]
    if cnt >= len(land)/2:
        print(army)
    else:
        print("SYJKGW")

 

그런데 조금 이상한게 과반수를 초과하는 경우에 그 군대가 땅을 지배하는 건데, 과반수여도 땅을 지배하게 해야 답이 나온다.

병사의 수를 세는데서 시간이 많이 걸리는데 Couter를 사용해서 간단하게 풀거나, 하나 하나 세줘도 된다.

다만, 셀 때는 list.count() 하면 런타임 에러가 나오므로 정렬 후 투포인터를 사용해야 한다.