[Python] 1270번 전쟁 - 땅따먹기

1270번: 전쟁 - 땅따먹기 (acmicpc.net)

1270번: 전쟁 - 땅따먹기

---

 

22/08/31

 

 

이 문제는 2가지 방법으로 풀 수 있는 좋은 문제이다.

 

기본적으로 시간제한이 10초여서 넉넉하게 풀 수 있을 거라고 생각하지만 의외로 시간이 많이 걸리기 때문에 O(n^2)의 알고리즘으로 문제를 풀면 시간 초과가 난다.

 

---

 

첫 번째 접근 방식:

 

 

처음에 문제를 접근했을 때에는 파이썬의 딕셔너리 자료형을 활용하면 금세 풀 수 있을 것이라고 생각했다.(아무리 생각해도 파이썬은 사기다)

 

리스트의 원소를 반복하여 입력받는데, 지금까지 나오지 않았던 병사의 번호가 새롭게 처음 나온다면 그 병사의 번호를 키로 하여 딕셔너리에 추가하고, 기존에 나왔던 병사의 번호가 나왔다면 그 키에 해당하는 값을 +1 해주는 식으로 구현했다.

 

마지막에 판단할 때 과반수인지 체크해주는 것까지 간단하게 구현할 수 있었다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

 

# 1270번 전쟁 - 땅따먹기
# 해시를 사용한 집합과 맵
import sys
input = sys.stdin.readline

N = int(input())
for _ in range(N):
    war = list(map(int, input().rstrip().split()))
    total_soldier = war[0]
    soldier_dic = {}
    for soldier_num in war[1:]:
        if soldier_num not in soldier_dic:
            soldier_dic[soldier_num] = 1
        else:
            soldier_dic[soldier_num] += 1
    if max(soldier_dic.values()) <= total_soldier//2:
        print('SYJKGW')
    else:
        print(max(soldier_dic, key=soldier_dic.get))

 

 

 

---

 

두 번째 접근 방식:

 

 

문제를 풀고 기여를 하려고 보니 '보이어-무어 다수결 투표'라는 태그가 붙어있었다.

 

왠지 이 알고리즘으로 문제를 풀면 기존의 딕셔너리 방법보다 쉽게 문제가 해결될 것 같아, 이를 활용하여 문제를 풀어보기로 했다.

 

자세한 내용은 이전에 작성해 놓은 보이어-무어 다수결 투표 알고리즘을 참고하면 도움이 될 것 같다.

 

[기타/etc.] 보이어-무어 다수결 투표 알고리즘(Boyer-Moore Majority Vote Algorithm) (tistory.com)

[기타/etc.] 보이어-무어 다수결 투표 알고리즘(Boyer-Moore Majority Vote Algorithm)

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1270번 전쟁 - 땅따먹기
# 보이어-무어 과반수 투표
import sys
input = sys.stdin.readline

def boyer_moore_majority(arr):
    count = 0 # 과반수의 원소가 몇개 있는가?
    major = 0 # 과반수의 원소
    for ele in arr:
        if count == 0:
            major = ele
        if major == ele:
            count += 1
        else:
            count -= 1
    if count == 0:
        return None, None
    k = len(arr)
    m = 0  # 정말 과반수 인지 체크용 변수
    for ele in arr:  # 정말 과반수가 맞는지 확인
        if ele == major:
            m += 1
    if m > k//2:
        return m, major # 과반수 원소가 몇개 있는지와 그 원소 반환
    else:
        return None, None

N = int(input())
for _ in range(N):
    war = list(map(int, input().rstrip().split()))
    major_num, major_ele = boyer_moore_majority(war[1:])
    if major_ele == None:
        print('SYJKGW')
    else:
        print(major_ele)