[BOJ] 1270 - 전쟁 - 땅따먹기 (Python)

 

 

아이디어 #1

 

딕셔너리를 이용하여 과반수인 병사 번호를 찾는다.

 

 

풀이 #1

 

import sys

input = sys.stdin.readline

def solution():
    n = int(input())
    for _ in range(n):
        T, *numbers = map(int, input().split())
        cnt_dict = dict()
        for number in numbers:
            temp = cnt_dict.get(number, 0)
            if temp >= T//2:
                print(number)
                break
            cnt_dict[number] = temp+1
        else:
            print('SYJKGW')

solution()

 

 

 

아이디어 #2

 

보이어-무어 다수결 투표 알고리즘을 이용하여 과반수인 병사 번호를 찾는다.

 

 

풀이 #2

 

import sys

input = sys.stdin.readline

def solution():
    n = int(input())
    for _ in range(n):
        T, *numbers = map(int, input().split())
        res = cnt = 0
        for number in numbers:
            if cnt == 0:
                res = number
            if number == res:
                cnt += 1
            else:
                cnt -= 1
        if numbers.count(res) > T//2:
            print(res)
        else:
            print('SYJKGW')

solution()