Language/Java

[백준 | Java] 1524번 세준세비 - Sort

ㅇ달빛천사ㅇ 2025. 2. 20. 10:29
728x90
1524번 / 세준세비

❓ 세준세비

🏷️ 관련 주제 : Sort


💦 나의 시도

PriorityQueue를 이용한 방법

  1. BufferedReader를 이용하여 테스트 케이스 개수를 입력 받아 int형으로 변환 후, int T에 할당
  2. 0 ~ (T - 1) 범위를 반복문을 돌면서 테스트 케이스 보기
  3. StringTokenizer를 이용하여 세준과 세비의 병사수 입력 받기
    • int N에 세준의 병사 수를 입력받아 int형으로 변환 후 할당
    • int M에 세비의 병사 수를 입력받아 int형으로 변환 후 할당
  4. PriorityQueue S 선언 : 세준의 병사를 담을 우선순위 큐
  5. PriorityQueue B 선언 : 세비의 병사를 담을 우선순위 큐
  6. StringTokenizer로 세준의 전체 병사 힘을 입력 받기
  7. 0 ~ (N - 1) 범위를 반복문을 돌면서 nextToken() 메서드를 이용하여 병사의 힘을 한개씩 S에 추가
  8. StringTokenizer로 세비의 전체 병사 힘을 입력 받기
  9. 0 ~ (M - 1) 범위를 반복문을 돌면서 nextToken() 메서드를 이용하여 병사의 힘을 한개씩 B에 추가
  10. S와 B가 모두 비어있지 않은 동안 반복문을 돌면서 세준과 세비의 병사 힘 비교
    • B의 제일 앞 원소가 S의 최상위 원소보다 작거나 같으면 B의 제일 앞 원소 제거(poll())
    • 그렇지 않으면 S의 제일 앞 원소 제거(poll())
  11. 한쪽의 우선순위 큐가 비었을 경우, 아직 우선순위 큐가 비지 않은 사람에 해당하는 알파벳을 BufferedWriter에 추가 후 줄바꿈
    • 세준의 우선순위큐가 비었으면 BufferedWriter에 "B"를 추가 후, 줄바꿈
    • 세비의 우선순위큐가 비었으면 BufferedWriter에 "S"를 추가 후, 줄바꿈
  12. BufferedWriter의 close() 메서드를 사용하여 결과값 출력하기

💥 런타임 에러(NoSuchElement)

에러 발생 이유를 파악하다가 '그냥 제일 강한 병사의 힘만 비교하면 그 힘이 더 센 쪽이 이기는게 아닌가?'라는 생각이 들었습니다.
그래서 Stream API를 이용하여 각 입력값의 최댓값만 가져와 비교하고 결과값을 출력하는 풀이를 작성해 보았습니다.

Stream API를 이용하여 가장 힘이 센 병사의 힘만 비교하여 승자를 결정하는 방법

int N, M에 입력값을 할당하는 것 까지는 동일

  1. Stream API를 이용하여 세준의 가장 강한 병사의 힘을 int S에 할당
    int S = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).max().getAsInt();
  2. Stream API를 이용하여 세비의 가장 강한 병사의 힘을 int B에 할당
    int B = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).max().getAsInt();
  3. 세준의 가장 강한 병사가 세비의 가장 강한 병사보다 세면(B <= S), BufferedWriter에 "S"를 추가하고 줄바꿈
  4. 그렇지 않으면(S < B>), BufferedWriter에 "B"를 추가하고 줄바꿈
  5. 모든 테스트 케이스의 승자를 구하고 반복문이 끝난 후, BufferedWriter의 close() 메서드를 사용하여 결과값 출력

💥 런타임 에러(NoSuchElement)

런타임 에러가 '각 테스트 케이스의 입력값 앞에 공백(줄바꿈)이 있어서 그런가?'해서
각 테스트 케이스를 도는 반복문 초기에 br.readLine() 추가
제출 성공!🎉

앞의 우선순위 큐를 이용한 방법도 br.readLine()을 추가하여 제출 성공🎉


Stream API를 이용하여 가장 강한 병사만 비교하는 방법에서 세비의 입력값을 하나씩 꺼낼 때,
세준의 가장 센 병사보다 강한 병사가 나오면 바로 승자가 결정되므로 완전 탐색하지 않아도 될 것 같아서
세비의 가장 강한 병사는 Stream API가 아닌 StringTokenizer에서 하나씩 꺼내서 비교하는 방법을 사용해 보았습니다.

세준만 Stream API를 이용, 세비의 병사는 StringTokenizer를 사용한 방법

세준의 가장 강한 병사를 구하는 데까지는 Stream API 만을 이용한 방법과 동일

  1. 세비의 가장 강한 병사의 힘을 담을 int B를 0으로 초기화
  2. st에 입력값을 할당
  3. StringTokenizer의 hasMoreTokens() 메서드를 사용하여 다음 토큰이 있는 동안 반복문 실행
    • B에 st의 nextToken() 값을 int형으로 변환 후, B에 할당
    • B가 세준의 가장 강한 병사 S보다 강하면 BufferedWriter에 "B"를 추가하고 줄바꿈 후, 반복문 종료(break;)
  4. 세비의 가장 강한 병사가 세준의 가장 강한 병사보다 약하거나 힘이 동일하면 BufferedWriter에 "S"를 추가하고 줄바꿈
  5. 모든 테스트 케이스가 끝난 후, BufferedWriter의 close() 메서드를 사용하여 결과값 출력

시간은 거의 동일했지만 메모리가 10000KB 정도 감소

📑제출 기록 및 오답 원인


💯 해결 방법

Stream API를 이용하여 제일 강한 병사만 비교하는 방법

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < T; i++) {
            br.readLine();
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int S = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).max().getAsInt();
            int B = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).max().getAsInt();

            if (B <= S) {
                bw.write("S");
                bw.newLine();
            } else {
                bw.write("B");
                bw.newLine();
            }
        }

        bw.close();
    }
}

Stream API와 StringTokenizer를 동시에 사용하는 방법

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < T; i++) {
            br.readLine();
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int S = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).max().getAsInt();
            int B = 0;
            st = new StringTokenizer(br.readLine());

            while (st.hasMoreTokens()) {
                B = Integer.parseInt(st.nextToken());

                if (B > S) {
                    bw.write("B");
                    bw.newLine();
                    break;
                }
            }

            if (B <= S) {
                bw.write("S");
                bw.newLine();
            }
        }

        bw.close();
    }
}

PriorityQueue를 이용하여 제일 약한 병사 제거하는 방법

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < T; i++) {
            br.readLine();
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            PriorityQueue<Integer> S = new PriorityQueue<>();
            PriorityQueue<Integer> B = new PriorityQueue<>();
            st = new StringTokenizer(br.readLine());

            while (st.hasMoreTokens()) {
                S.add(Integer.parseInt(st.nextToken()));
            }

            st = new StringTokenizer(br.readLine());

            while (st.hasMoreTokens()) {
                B.add(Integer.parseInt(st.nextToken()));
            }

            while (!S.isEmpty() && !B.isEmpty()) {
                if (B.peek() <= S.peek()) {
                    B.poll();
                } else {
                    S.poll();
                }
            }

            if (S.isEmpty()) {
                bw.write("B");
                bw.newLine();
            } else {
                bw.write("S");
                bw.newLine();
            }
        }

        bw.close();
    }
}
728x90
저작자표시 비영리 변경금지 (새창열림)