[99클럽 4기 코테 스터디 TIL 30일차] 세준세비 (feat. 최소힙)

1) 문제

https://www.acmicpc.net/problem/1524

 

세준이와 세비는 온라인 게임을 즐겨한다. 이 온라인 게임에서는 군대를 서로 키울 수 있다. 세준이는 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

 

 

2) 내가 구현한 코드

import java.io.*;
import java.util.*;

public class p1524_세준세비 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine()); // 테스트 진행횟수
        for (int i = 0; i < T; i++) {
            br.readLine(); // 빈 줄 처리
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // S 병사 수
            int M = Integer.parseInt(st.nextToken()); // B 병사 수

            PriorityQueue<Integer> sp = new PriorityQueue<>(); // 세준이 병사
            PriorityQueue<Integer> bp = new PriorityQueue<>(); // 세비 병사

            // 세준이 병사 능력치 입력
            st = new StringTokenizer(br.readLine());
            for (int s = 0; s < N; s++) {
                sp.add(Integer.parseInt(st.nextToken()));
            }

            // 세비 병사 능력치 입력
            st = new StringTokenizer(br.readLine());
            for (int b = 0; b < M; b++) {
                bp.add(Integer.parseInt(st.nextToken()));
            }

            // 전투 진행
            while (!sp.isEmpty() && !bp.isEmpty()) {
                if (sp.peek() >= bp.peek()) {
                    bp.poll(); // 세비 병사 제거
                } else {
                    sp.poll(); // 세준이 병사 제거
                }
            }

            // 결과 출력
            if (sp.isEmpty() && bp.isEmpty()) {
                bw.write("C\n"); // 둘 다 없음 (무승부)
            } else if (sp.isEmpty()) {
                bw.write("B\n"); // 세준이 병사 없음
            } else {
                bw.write("S\n"); // 세비 병사 없음
            }
        }

        bw.flush();
        br.close();
        bw.close();
    }
}

 

 

3) 추가 문제

미들러 - 상자넣기

https://www.acmicpc.net/problem/1965

챌린저 - 택배 배달과 수거하기

https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스