[백준] no1927: 최소 힙

문제

: 최소값을 0의 개수만큼 출력 (단, 배열이 빈 값이면 0을 출력)

 

문제 링크 : https://www.acmicpc.net/problem/1927

---

원리

우선순위 큐

---

풀이방법

1. HashSet을 이용한 Stream으로 min구하는 방법 [시간초과]

2. PriorityQueue로 최소값 구하는 방법 [성공]

---

나의 코드

1. HashSet + Stream 조합

public class no1927 {

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

        int T = Integer.parseInt(br.readLine());
        Set<Integer> set = new HashSet<>();

        for(int i=0; i<T ; i++) {
            Integer num = Integer.parseInt(br.readLine());
            if(num.equals(0)) {
                if(set.isEmpty()) bw.write("0\n");
                else{
                    Integer min = set.stream().mapToInt(a -> a).min().getAsInt();
                    bw.write(""+ min +"\n");
                    set.remove(min);
                }
            } else {
                set.add(num);
            }
        }
        bw.close();
    }
}

2. 우선순위 큐 방법 

public class no1927 {

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

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        PriorityQueue<Integer> que = new PriorityQueue<>(); // 우선순위 큐

        for(int i=0; i<T ; i++) {
            Integer num = Integer.parseInt(br.readLine()); // 입력된 숫자
            if(num.equals(0)) {                            // 입력이 0일 경우,
                if(que.isEmpty()) bw.write("0\n");     //  1. 큐가 비어있으면 0을 출력
                else bw.write(""+ que.poll() +"\n");   //  2. 큐에 숫자가 있으면, 제일 작은수가 맨 앞에 와있으므로 바로 poll()
            } else que.add(num);                           //  입력이 0이 아닌 경우, que에 넣음
        }
        bw.close(); // 출력
    }
}