[Python] 백준/BOJ 1270번: 전쟁 - 땅따먹기 (Silver 3)

💻 Problem

문제 보러 가기

 

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

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

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

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

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

 

💡 Approach

파이썬의 Counter를 활용해 각 군대 번호가 몇 번 등장하는지 센다.

가장 많이 등장한 군대의 횟수가 과반수를 넘으면 해당 군대 번호를 출력한다.

과반수를 넘지 않으면 “SYJKGW”를 출력한다.

 

army = max(Counter(ground[1:]).items(), key=lambda x:x[1])

처음에는 max()의 key를 활용해서 value를 기준으로 가장 큰 값을 구했다.

 

army = Counter(ground[1:]).most_common(1)[0]

max()가 아니라 most_common()을 쓰는 방법도 있었다.

Counter 모듈에는 most_common()이 존재하는데 이를 활용하면 최빈값을 구할 수 있다고 한다.

 

✏️ Solution

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

for _ in range(int(input())):
    ground = list(map(int, input().split()))
    army = Counter(ground[1:]).most_common(1)[0]
    print(army[0] if army[1] > ground[0] // 2 else 'SYJKGW')

 ⏱️ 시간복잡도

• 땅의 개수: n (n <= 200)
• 각 땅의 병사 수: Ti (Ti <= 100,000)

1. n: 땅의 개수 최대 200
2. Ti: 한 줄에 최대 100,000개의 군대
3. Ti + Ti: 군대 번호들에 대해 빈도 계산 + 최빈값 찾기

시간복잡도는 Ti의 합이지만 최악의 경우는 n * Ti가 된다.

200 * 100,000 = 2 * 10^7