오늘의 학습 키워드
https://www.acmicpc.net/problem/1524
문제
세준이와 세비는 온라인 게임을 즐겨한다. 이 온라인 게임에서는 군대를 서로 키울 수 있다. 세준이는 N명의 병사를 키웠고, 세비는 M명의 병사를 키웠다.
이제 서로 전쟁을 하려고 한다.
전쟁은 여러 번의 전투로 이루어진다. 각 전투에서 살아있는 병사중 제일 약한 병사가 죽는다. 만약 제일 약한 병사가 여러 명이고, 제일 약한 병사가 모두 같은 편에 있다면, 그 중에 한 명이 임의로 선택되어 죽는다. 하지만, 제일 약한 병사가 여러 명이고, 양 편에 모두 있다면, 세비의 제일 약한 병사 중 한 명이 임의로 선택되어 죽는다.
전쟁은 한 명의 병사를 제외하고 모두 죽었을 때 끝난다. 전쟁의 승자를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 100보다 작거나 같다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 첫째 줄에 N과 M이 들어오고, 둘째 줄에는 세준이의 병사들의 힘이 들어오고, 셋째 줄에는 세비의 병사들의 힘이 들어온다. 힘은 정수이고, 이 값이 클수록 강하고, 작을수록 약하다.
각 테스트 케이스는 줄 바꿈으로 구분되어 있다.
출력
각 테스트 케이스에 대해서 한 줄에 하나씩 차례대로 승자를 출력한다. 세준이가 이기면 S를 세비가 이기면 B를 둘다 아닐 경우에는 C를 출력한다.
- 완주하지 못
공부한 내용 본인의 언어로 정리하기
문제분석
- 세준과 세비의 병사 중 제일 약한들 끼리 매치해 더 약한 병사는 죽는다.
- 양쪽에 제일 약한 병사 있다면 그때는 세비의 병사가 죽는다.
- 그러므로 세준이의 병사가 죽는 경우는 세준이에 병수가 세비보다 약할 경우이며 나머지는 세비의 병사가 죽는다.
접근 방법
- 주어진 병사의 능력치 별로 정렬할 수 있는 자료구조가 필요하며, 그것을 오름차순으로 정렬되어 있어야 한다.
- 우선순위 큐를 활용할 예정이며, 큐이므로 약한 병사에 대해 데이터를 빼낼 수 있다.
구현 코드
package backjoon.bronze.lv1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class B1524 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < t; i++) {
br.readLine(); // 빈 줄 처리
// N과 M 입력
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 세준 병사들의 힘 입력
PriorityQueue<Integer> sejun = new PriorityQueue<>();
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
sejun.add(Integer.parseInt(st.nextToken()));
}
// 세비 병사들의 힘 입력
PriorityQueue<Integer> sebi = new PriorityQueue<>();
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
sebi.add(Integer.parseInt(st.nextToken()));
}
while (!sejun.isEmpty() && !sebi.isEmpty()) {
if(sejun.peek() < sebi.peek()) {
sejun.poll();
} else {
sebi.poll();
}
}
if(sejun.isEmpty()){
sb.append("B\n");
} else{
sb.append("S\n");
}
}
System.out.print(sb);
}
}
코드 설명
- 우선순위 큐 사용:
- 세준과 세비 병사의 힘을 각각 PriorityQueue에 저장한다.
- PriorityQueue는 기본적으로 오름차순 정렬되므로 가장 약한 병사를 쉽게 꺼낼 수 있다.
- 전투 시뮬레이션:
- 두 병사의 힘을 비교한다.
- 더 약한 병사를 제거 (poll())하면서 전투를 진행한다.
- 병사 중 한 쪽이 모두 탈락하면 종료한다.
- 결과 출력:
- 세준 병사가 모두 탈락했으면 B(세비 승리), 세비 병사가 모두 탈락했으면 S(세준 승리)를 출력한다.
오늘의 회고
이력서 주차 마지막이다. 내 이력서가 어느정도 완성되었지만 부족한 부분이 보인다. 그것을 과정 끝나기까지 채웠으면 좋겠다.
- 완주하지
