[문제 풀이] 백준 1270 전쟁 - 땅따먹기
문제 설명
현재 여러 지역은 한창 전쟁이 벌어지고 있는 상황인데, 어느 지역은 거의 전쟁이 마무리 단계로 가고 있다.
하지만 당신은 군대를 보낼 때 적군을 혼란시키기 위해서 우리 나라의 군대라는걸 표시하지 않고, 군대의 번호로 표시했다.
어느 땅에서 한 번호의 군대의 병사가 절반을 초과한다면 그 땅은 그 번호의 군대의 지배하에 놓이게 된다.
이때, 각 땅들을 지배한 군대의 번호를 출력하여라. 만약, 아직 전쟁이 한창중인 땅이라면 “SYJKGW”을 쌍 따옴표 없이 출력한다.
변수 설명
- n
- 타입 : int
- 저장 데이터 : 땅의 개수 입력 후 저장
- t
- 타입 : list
- 저장 데이터 : 최대 병사 수, 병사들을 한줄에 입력 후 저장
- land_t
- 타입 : int
- 저장 데이터 : 땅의 군사 수의 절반을 저장
- land_dic
- 타입 : dictionary
- 저장 데이터 : 그 땅의 군대를 키로 받고 그 군대의 병사 수를 value로 저장
풀이과정
-
땅의 개수 입력 (n)
-
최대 병사 수, 병사들을 한줄에 입력 (t)
-
land_t 에 땅의 최대 병사의 절반을 저장 이때 정수형이여야 하므로 // 로 나눈다.
-
for문을 통해 len(t)만큼 반복하며 land_dic에 키와 값을 업데이트
-
max_t 에 가장 많은 병사를 가진 key 값을 저장
-
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
를 종종 사용해야겠다!
Author And Source
이 문제에 관하여([문제 풀이] 백준 1270 전쟁 - 땅따먹기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soshin_dev/문제-풀이-백준-1270-전쟁-땅따먹기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)