세준세비
문제
세준이와 세비는 온라인 게임을 즐겨한다. 이 온라인 게임에서는 군대를 서로 키울 수 있다. 세준이는 N명의 병사를 키웠고, 세비는 M명의 병사를 키웠다.
이제 서로 전쟁을 하려고 한다.
전쟁은 여러 번의 전투로 이루어진다. 각 전투에서 살아있는 병사 중 제일 약한 병사가 죽는다. 만약 제일 약한 병사가 여러 명이고, 제일 약한 병사가 모두 같은 편에 있다면, 그 중에 한 명이 임의로 선택되어 죽는다. 하지만, 제일 약한 병사가 여러 명이고, 양 편에 모두 있다면, 세비의 제일 약한 병사 중 한 명이 임의로 선택되어 죽는다.
전쟁은 한 명의 병사를 제외하고 모두 죽었을 때 끝난다. 전쟁의 승자를 출력하는 프로그램을 작성하시오.
입력
- 첫째 줄에 테스트 케이스의 개수
T가 주어진다.T는 100보다 작거나 같다. - 각 테스트 케이스는 다음과 같이 이루어져 있다:
- 첫째 줄에
N과M이 들어온다. - 둘째 줄에는 세준이의 병사들의 힘이 들어온다.
- 셋째 줄에는 세비의 병사들의 힘이 들어온다.
- 첫째 줄에
- 힘은 정수이고, 이 값이 클수록 강하고, 작을수록 약하다.
- 각 테스트 케이스는 줄 바꿈으로 구분되어 있다.
출력
각 테스트 케이스에 대해서 한 줄에 하나씩 차례대로 승자를 출력한다:
- 세준이가 이기면
S - 세비가 이기면
B - 둘 다 아닐 경우에는
C를 출력한다.
제한
- 1 ≤
N,M≤ 1,000,000 - 병사들의 힘은 300,000,000보다 작거나 같은 자연수이다.
예제 입력 1
2
1 1
1
1
3 2
1 3 2
5 5
예제 출력 1
S
B
<내 코드>
import sys
# 1-1. 게임 횟수 입력
games = int(sys.stdin.readline())
# 1-2. 세준 N, 세비 M 명 병사 (같을 경우 세바 병사 사망)
for _ in range(games):
sys.stdin.readline().strip()
NM = list(map(int,sys.stdin.readline().split()))
# 1-3. 세준 병사의 힘들, 세바 병사 들의 힘들 입력 & 정렬
Jn_armies = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
Bm_armies = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
# 2. 게임 진행
while Jn_armies and Bm_armies:
if Jn_armies[-1] < Bm_armies[-1]:
n_army = Jn_armies.pop()
else:
m_army = Bm_armies.pop()
if Jn_armies:
sys.stdout.write("S\n")
# print("S")
elif Bm_armies:
sys.stdout.write("B\n")
# print("B")- 깨달은점
처음에는 pop() 을 생각했는데 그냥 인덱스로 조회를 하고 해당조건이 만족했을 때 꺼재는 방식이 IndexError을 방지하고 바람직한것 같다.
pop() 을 하지만 2중반복문으로 들어가면 O(n^2) 의 문제가 발생할 수있음
<모범 사례>
import sys
T = int(sys.stdin.readline())
for _ in range(T):
# 빈 줄을 건너뛰며 N과 M을 읽습니다.
while True:
line = sys.stdin.readline()
if not line:
break # EOF 처리
if line.strip() != '':
N, M = map(int, line.strip().split())
break
# 세준이의 병사들의 힘을 읽습니다.
sejun_armies = []
while len(sejun_armies) < N:
line = sys.stdin.readline()
if not line:
break
sejun_armies.extend(map(int, line.strip().split()))
# 세비의 병사들의 힘을 읽습니다.
sebi_armies = []
while len(sebi_armies) < M:
line = sys.stdin.readline()
if not line:
break
sebi_armies.extend(map(int, line.strip().split()))
# 전쟁 결과 판정
max_sejun = max(sejun_armies)
max_sebi = max(sebi_armies)
if max_sejun >= max_sebi:
print("S")
else:
print("B")- 전제 전투를 안돌리고, 가장 큰값만 비교해서 결과 도출함
max() 는 O(N) 의 시간복잡도 가능
어차피 가장 강한쪽이 있으면 다른 변수가 없으니 결과는 모두 동일함
- 문제에 대한 원리를 이해하면 가능함