[백준/Python] 1270. 전쟁 - 땅따먹기

문제 링크

 https://www.acmicpc.net/problem/1270

1270번: 전쟁 - 땅따먹기

 

---

문제 풀이

 접근 방식은 다음과 같았다.

1. 배열을 선언, 숫자를 입력받고 그 중에서 최빈값을 구한다.
2. 최빈값이 Ti의 절반을 넘어가는지 판단 후 출력 조건에 맞춰 출력.

 그런데, n과 Ti의 입력 범위를 보고 1번을 이렇게 수정했다.

 1. 배열을 선언, 숫자를 입력받고 그 중에서 최빈값을 구한다. 
 1-1. 배열에서 최빈값을 구하는데 걸리는 시간은 정렬되지 않았다면 O(n^2)만큼 걸린다. 100억번의 연산을 200번 하게 될 수도 있으니 다른 방법을 찾아보자.
 1-2. 그렇다면 배열을 정렬하고 최빈값을 구하는 방법은 어떨까? 일반적인(퀵,병합 등) 정렬(O(nlogn))로 정렬한 뒤 n번 비교한다. 총 시간 복잡도 = O(nlogn)
충분히 좋은 접근 방법이지만 스터디 중 배운 자료구조인 딕셔너리를 통해 문제를 해결해 보았다.

 왜 딕셔너리를 사용했는가?

 배열을 사용하게 되면 원소의 내용. 즉, 병사의 번호만 저장할 수 있는 반면 딕셔너리를 사용하게 되면 병사의 번호(key)와 병사의 수(value)를 동시에 저장할 수 있다. 그럼 1-2 방법에서 진행한 정렬 후 비교 작업을 따로 하지 않아도 된다.
결정적으로 정렬이 필요없기 때문에 1-2 방법보다 시간적인 측면에선 좋다고 볼 수 있다. (메모리 공간은 그저 지못미..)

 

코드

n = int(input())

for _ in range(n):
    d = dict()
    line = input().split()
    t = int(line[0])
    max_val = 0
    max_key = 0 
    for i in range(1, len(line)):
        num = int(line[i])
        if num not in d:
            d[num] = 1
        else:
            d[num] += 1
        if d[num] > max_val:
            max_val = d[num]
            max_key = num
    if max_val > t / 2:
        # 전쟁 끝
        print(max_key)
    else:
        print('SYJKGW')