1. 문제
[문제 설명]
세준이와 세비는 온라인 게임을 즐겨한다. 이 온라인 게임에서는 군대를 서로 키울 수 있다. 세준이는 N명의 병사를 키웠고, 세비는 M명의 병사를 키웠다.
이제 서로 전쟁을 하려고 한다.
전쟁은 여러 번의 전투로 이루어진다. 각 전투에서 살아있는 병사중 제일 약한 병사가 죽는다. 만약 제일 약한 병사가 여러 명이고, 제일 약한 병사가 모두 같은 편에 있다면, 그 중에 한 명이 임의로 선택되어 죽는다. 하지만, 제일 약한 병사가 여러 명이고, 양 편에 모두 있다면, 세비의 제일 약한 병사 중 한 명이 임의로 선택되어 죽는다.
전쟁은 한 명의 병사를 제외하고 모두 죽었을 때 끝난다. 전쟁의 승자를 출력하는 프로그램을 작성하시오.
[입력]
각 테스트 케이스에 대해서 한 줄에 하나씩 차례대로 승자를 출력한다. 세준이가 이기면 S를 세비가 이기면 B를 둘다 아닐 경우에는 C를 출력한다.
[출력]
각 테스트 케이스에 대해서 한 줄에 하나씩 차례대로 승자를 출력한다. 세준이가 이기면 S를 세비가 이기면 B를 둘다 아닐 경우에는 C를 출력한다.
[제한]
- 1 ≤ N, M ≤ 1,000,000
- 병사들의 힘은 300,000,000보다 작거나 같은 자연수이다.
[입출력 예]
2. 풀이
import sys
T = int(sys.stdin.readline().strip())
for _ in range(T):
N, M = map(int, sys.stdin.readline().split())
SJ = map(int, sys.stdin.readline().split())
SB = map(int, sys.stdin.readline().split())
SJ.sort()
SB.sort()
# 투 포인터 방식으로 전투 진행
i, j = 0, 0
while i < N and j < M:
if SJ[i] < SB[j]:
i += 1 # 세준이의 병사 제거
else:
j += 1 # 세비의 병사 제거 (둘이 같으면 세비가 제거됨)
if i < N: # 세준이 병사가 남아있음
print('S')
elif j < M: # 세비의 병사가 남아있음
print('B')
else:
print('C') # 둘다 아님3. 회고
3-1. 문제 해결 과정
문제를 맞게 풀었다 생각했는데 틀렸다길래 뭔가 했더니 전투 규칙을 빼먹었다. 가장 약한 병사부터 제거한다고 했으니 세준이와 세비의 병사를 비교하면서 한 명씩 제거해야 한다.
비교를 위해 투 포인터 방식을 사용했다. 말 그대로 두 개의 포인터를 사용해서 리스트를 순회하는 형식으로 전투를 진행한다. 첫 시작은 모두 0, 0으로 시작한다.
while i < N and j < M:
if SJ[i] < SB[j]:
i += 1 # 세준이의 병사 제거
else:
j += 1 # 세비의 병사 제거 (둘이 같으면 세비가 제거됨)제일 약한 병사가 둘다 대치 중일 경우에는 세비의 병사를 제거한다는 규칙을 고려하여 위와 같이 코드를 작성했다. 막상 코드 작성을 마치니 생각보다 어려운 편은 아니었다.
3-2. 새롭게 배운 내용
-
투 포인터 : 두 개의 포인터(인덱스)를 사용하여 배열을 탐색하는 방법이다.
-
strip(): 문자열의 앞 뒤에 있는 공백이나 개행 문자\n를 제거하는 함수이다.input()및sys.stdin.readline()을 사용할 때strip()을 이용하면 불필요한 공백 없이 깔끔하게 처리할 수 있다.
