[문제 풀이] BOJ - 1270 전쟁 - 땅따먹기

문제 설명

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

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

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

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

---

변수 설명

• n

  • 타입 : int
  • 저장 데이터 : 땅의 개수 입력 후 저장

• t

  • 타입 : list
  • 저장 데이터 : 최대 병사 수, 병사들을 한줄에 입력 후 저장

• land_t

  • 타입 : int
  • 저장 데이터 : 땅의 군사 수의 절반을 저장

• land_dic

  • 타입 : dictionary
  • 저장 데이터 : 그 땅의 군대를 키로 받고 그 군대의 병사 수를 value로 저장

  ---

  풀이과정

  1. 땅의 개수 입력 (n)
  2. 최대 병사 수, 병사들을 한줄에 입력 (t)
  3. land_t 에 땅의 최대 병사의 절반을 저장 이때 정수형이여야 하므로 // 로 나눈다.
  4. for문을 통해 len(t)만큼 반복하며 land_dic에 키와 값을 업데이트
  5. max_t 에 가장 많은 병사를 가진 key 값을 저장
  6. land_t 값 보다 land_dic[max_t] 값이 크면 max_t 값을 출력
     작으면 "SYJKGW" 를 출력한다.

  ** 위 과정을 n 만큼 반복 **

  ---

  

---

코드

  import sys

n = int(sys.stdin.readline())  # 땅의 개수

for _ in range(n):
    t = list(map(int, sys.stdin.readline().split()))  # 땅의 병사수 및 병사 군대 번호 입력
    land_t = t[0] // 2
    land_dic = {}
    temp = 0
    for i in range(1, len(t)):
        if t[i] in land_dic:
            land_dic[t[i]] += 1
        else:
            land_dic[t[i]] = 1

    max_t = max(land_dic, key=land_dic.get)

    if land_dic[max_t] > land_t:
        print(max_t)
    else:
        print("SYJKGW")

---

배운점

처음 구현을 할때, 전에 풀던 것 중 List comprehension 을 통해 하면 속도가 더 빠르다고 하여 처음 병사 수와 병사 군대 번호를 입력받는 t를 이중 리스트로 전부 입력을 받았더니 메모리 초과가 떴다..

그래서 다시 이번엔 for문을 통해 한줄 한줄 입력받는 형식으로 바꾸었고 위 처럼 코드를 작성하였다.

처음 max를 통해 dictionary의 value를 비교해 key 값을 출력하려고 했지만
max 는 key를 기준으로 가장 큰 값을 찾아주기 때문에 옵션에 key=dict.get 옵션을 추가해주어 value를 기준으로 key값을 반환하게 만들었다.

하지만 위처럼 구현하게 된다면 속도가 너무 느리게 구현이 된다.

그래서 속도를 더 빠르게 할 수 있는 방법을 구현하기 위해 찾아보니 collections의 Counter 를 사용하면 된다고 하여 코드를 다시 재구성 하기로 했다.

Counter는 iterable 객체를 값으로 받아 dictionary형태의 카운터 객체를 반환해준다.
이때 Counter.most_common(n) 을 사용하면 Counter 객체의 빈도, 즉 value 중 상위 n 개의 값을 반환해준다.

그래서 Counter를 사용해서 코드를 구현하면 아래와 같아 진다.

  import sys
from collections import Counter

n = int(sys.stdin.readline())  # 땅의 개수

for _ in range(n):
    t = list(map(int, sys.stdin.readline().split()))  # 땅의 병사수 및 병사 군대 번호 입력
    land_t = int(t[0]) / 2
    t_list = t[1:]

    max_t = Counter(t_list).most_common(1)

    if max_t[0][1] > land_t:
        print(max_t[0][0])
    else:
        print("SYJKGW")

코드가 짧아졌을 뿐 더러 속도도 향상 된 것을 알 수 있다!

위 처럼 이젠 iterable 객체에 관한 문제에서는 Counter를 종종 사용해야겠다!