[BOJ][Python]1270 풀이

1270번: 전쟁 - 땅따먹기

import sys
from collections import defaultdict
ssr = sys.stdin.readline

n = int(ssr())
for _ in range(n):
    t = list(map(int, ssr().split()))
    cnt = defaultdict(int)
    sol = defaultdict(list)
    for i in range(1, len(t)):
        cnt[t[i]] += 1
    for key, value in cnt.items():
        sol[-value].append(key)
    for key, value in sorted(sol.items()):
        if -key > t[0]//2 and len(value) == 1:
            print(value[0])
            break
        else:
            print('SYJKGW')
            break

'''
보이어-무어 과반수 투표 알고리즘에 대해 찾아볼 것
'''

최근에 계속 하루에 하나씩 문제를 풀고 있는데 오늘은 다른 일이 바빠서 조금 늦게 시작했더니 결국 날이 바뀌었네요. 이번에는 반쪽짜리 풀이입니다. 코드 아래에도 써놓았지만 런타임이 짧은 코드는 대부분 이 알고리즘을 사용한 것 같더라구요. 

 

제가 푼 방법은 사실 크게 어려울 건 없고 어제 사용했던 defaultdict의 연장이라고 보시면 될 것 같습니다. 사실 counting sort를 쓰고 싶었는데 j가 몇 번 까지 나온다는 것에 대한 보장이 없어서 사용을 할 수가 없을 것 같습니다. 매 테스트케이스마다 배열을 새로 만드는 것도 비효율적이구요.

 

따라서 문제 자체는 그냥 시키는대로 해주면 됩니다. 시간제한도 사실 10초라 엄청 넉넉해요. 주는 입력을 받고, 개수를 세어서 리스트든 딕셔너리든 알아볼 수 있게 저장을 해줍니다. 그 다음부터는 사람마다 조금씩 다를 수 있겠지만 저는 딕셔너리를 하나 더 만들어서, 같은 개수가 나온 번호를 값으로, 그 개수를 key로 하는 딕셔너리를 생성했습니다. 이렇게 하면 과반수가 넘는 번호가 몇 번인지 또 몇개인지 파악할 수 있겠죠. 그러면서 그냥 코드를 좀 편하게 작성하기 위해 cnt의 밸류를 음수로 바꿔 sol의 키로 저장합니다. 그러면 제일 많은 개수가 제일 작은 개수가 되어서 sorted 했을 때 제일 앞에 나오겠죠(오름차순이니까). sorted를 쓰지 않으면 key가 뒤죽박죽일테니 제일 많은 개수의 원소를 따로 찾아주는 코드를 작성해야하고, -value를 하지 않으면 정렬할 때 내림차순으로 정렬하는 코드를 추가해야겠죠. 그래서 -를 붙여줬습니다. 그러고 나면 끝입니다. 제일 먼저 나오는 key가 제일 많은 개수를 가진 번호니까 그 번호만 확인하고 break 해주면 형태는 반복문이지만 반복문은 아닌거죠. 그렇다고 반복문을 안쓰자니 key나 value를 호출할 때 sorted~하면서 다 써줘야 하구요. 코드를 짧게 하기 위한 꼼수들이 좀 들어갔습니다만, 그 외에는 그다지 보기 어려운 것 없을 것 같습니다.

 

추가//

보이어-무어 과반수(다수결) 알고리즘에 대해 공부하고 왔습니다. 보이어-무어 과반수 알고리즘(Boyer-Moore Majority Algorithm)은 결과가 무조건 과반수일 가능성이 있는 원소가 되는 알고리즘입니다. 굳이 가능성이 있는 이라는 말을 강조하는 이유는 결과가 항상 과반수라는 보장이 안되기 때문이며 해당 예시를 코드와 함께 소개해보도록 하겠습니다. https://sgc109.github.io/2020/11/30/boyer-moore-majority-vote-algorithm/ 해당 알고리즘을 이해하는데에 큰 도움을 준 포스팅을 함께 첨부합니다.

import sys
ssr = sys.stdin.readline

def boyer_moore_majority(t):
    major = 0
    cnt = 0
    for i in range(1, len(t)):
        if cnt == 0:
            major = t[i]
            cnt += 1
        else:
            if t[i] == major:
                cnt += 1
            else:
                cnt -= 1
    check = t[1:].count(major)
    if check > t[0]//2:
        print(major)
    else:
        print('SYJKGW')

n = int(ssr())
for _ in range(n):
    t = list(map(int, ssr().split()))
    ans = boyer_moore_majority(t)

이 문제를 과반수 알고리즘을 이용해 푼 코드입니다. 알고리즘을 간단히 소개하자면, 배열의 원소를 하나씩 확인하면서 과반수 후보를 갱신하고 다음에 나올 원소가 현재의 과반수 후보와 같다면 카운트를 올리고 다르다면 카운트를 내립니다. 이 때 카운트가 이미 0이라면 후보를 변경하는 과정을 거칩니다. 예를 들어서 예제 1의 첫번째 케이스를 확인해보겠습니다.

1 2 3 1 2 3 1 2 3 1 의 입력이 주어지면,

index = 1 일 때, major = 1, cnt = 1(처음이니까 후보 갱신과 카운트 증가)

index = 2 일 때, major = 1, cnt = 0(입력과 후보가 다르고 카운트가 1이므로 하나 깎음)

index = 3 일 때, major = 3, cnt = 1(카운트가 0이므로 후보 갱신과 카운트 증가)

index = 4 일 때, major = 3, cnt = 0(입력과 후보가 다르고 카운트가 1이므로 하나 깎음)

...

이렇게 카운트도 변하고 후보도 변하면서 O(N)의 시간복잡도로 확인이 가능한 알고리즘입니다. 그렇다면 마지막에 major라고 되어있는 수가 과반수일 가능성이 있다는 건 어떻게 보장할 수 있을까요? 순서를 좀 바꿔서 넣으면 이게 바뀔 수도 있지 않을까요? 입력이 11223333과 31313232를 확인해보겠습니다(참고로 가장 많은 수가 나와도 애초에 전체 길이의 절반이 아니라면 순서에 따라 결과에 가장 많은 수가 나오지 않을 수 있습니다. ex.3331122 결과 : 2, 1122333 결과 : 3).

11223333	31313232
major = 1, cnt = 1	major = 3, cnt = 1
major = 1, cnt = 2	major = 3, cnt = 0
major = 1, cnt = 0	major = 3, cnt = 1
major = 1, cnt = 0	major = 3, cnt = 0
major = 3, cnt = 1	major = 3, cnt = 1
major = 3, cnt = 2	major = 3, cnt = 0
major = 3, cnt = 3	major = 3, cnt = 1
major = 3, cnt = 4	major = 3, cnt = 2

순서가 바뀌더라도 전체 배열 크기의 절반 만큼 등장하면 결과는 과반수 후보가 나오게 됩니다. 왜 위에서 굳이 가능성이 있는 이라고 말했는지 이제 아시겠죠. 그래서 우리는 후보를 찾은 다음에 이 후보가 진짜 과반수를 넘는지 아닌지 한 번 더 체크를 해줘야 합니다. 그래서 저는 count 메서드를 써서 체크를 해줬습니다.

 

알고리즘 이름이 생소해서 그렇지 별로 어렵지는 않죠? 위에서 첨부한 링크의 포스팅이 너무 좋은 것도 한 몫 했겠지만 이해하기 어렵지도 않고 구현도 간단합니다. 한 번 정도 읽어보고 직접 짜보면 바로 이해되실거에요.