글 읽기 - 안녕하세요. 9935번 문제로, 선배님들의 도움이 필요합니다...

chickenman10 2년 전 0

안녕하세요. 이번년도 코테를 준비하기 시작한 코내기입니다.

이번에 문제를 풀어보는데 도저히 어디서 오류가 나는지 제가 생각한 모든 반례를 들어봐도 틀렸다고 나오네요(특히 2%..ㅎㅎ)

어디서 틀린건지 알려주시면 정말 감사드리겠습니다!!

코드를 대략적으로 설명해보자면

1) 처음 받은 모든 문자열을 문자 크기순으로 오름차순으로 정렬하여 min heap(str)에 넣습니다.

2) 마찬가지로 폭탄 문자열도 문자 크시순으로 오름차순으로 정렬하여 저장(hboom)합니다.

3) 결과를 출력할때 기존의 순서대로 출력하기 위한 인덱스의 오름차순으로 정렬하여 min heap(rs)에 넣어줍니다.

4) 가장 작은 폭탄 문자를 꺼내서 그것보다 작은 문자들을 rs에 넣어줍니다. 만약 이 while문 이후 str이 비었다면 가장

작은 폭탄 보다 모든 문자열의 문자가 작단것을 의미하기때문에 종료합니다.

그 후, 폭탄 문자와 같은 문자들을 문자열에서 제거합니다.

5) 마지막 while문을 통해 폭탄 문자를 모두 제거하고 남은 문자열의 문자들을 rs에 저장합니다.

ex) 정렬후 str : 1233abcd, hboom : 3bd

-> 폭탄 : 3 | 1,2는 rs에 저장, 3,3을 str에서 제거

-> 폭탄 : b | a를 rs에 저장, b를 str에서 제거

-> 폭탄 : d | c를 rs에 저장, d를 str에서 제거

=> 결론 : 12ac

긴 글 읽어주셔서 감사합니다.

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

public class P9935 {
    public static class ArrChar{
        private char c;
        private int idx;

        public ArrChar(char c, int idx) {
            this.c = c;
            this.idx = idx;
        }
    }
    public static void cal(PriorityQueue<ArrChar> rs, PriorityQueue<ArrChar> str, char b){
        while(!str.isEmpty() && str.peek().c < b) {
            rs.add(str.poll());
        }
        if(str.isEmpty()) return;

        while(b == str.peek().c) {
            str.poll();
            if (str.isEmpty()) return;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String input = br.readLine();
        PriorityQueue<ArrChar> str = new PriorityQueue<>(new Comparator<ArrChar>() {
            @Override
            public int compare(ArrChar o1, ArrChar o2) {
                return o1.c - o2.c;
            }
        });
        for(int i = 0; i < input.length(); i++)
            str.add(new ArrChar(input.charAt(i), i));

        String boom = br.readLine();
        PriorityQueue<Character> hboom = new PriorityQueue<>();
        for(int i = 0; i < boom.length(); i++)
            hboom.add(boom.charAt(i));

//        System.out.println(hboom);

        PriorityQueue<ArrChar> rs = new PriorityQueue<>(new Comparator<ArrChar>() {
            @Override
            public int compare(ArrChar o1, ArrChar o2) {
                return o1.idx - o2.idx;
            }
        });
        while(!hboom.isEmpty() && !str.isEmpty()){
            char b = hboom.poll();
            cal(rs, str, b);
        }

        while(!str.isEmpty())
            rs.add(str.poll());

        if(rs.isEmpty()) bw.write("FRULA");
        else {
            while(!rs.isEmpty())
                bw.write(rs.poll().c);
        }
        bw.flush();
        br.close();
        bw.close();
    }
}

댓글을 작성하려면 로그인해야 합니다.