[BOJ 백준] - 펭귄추락대책위원회 Java

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

문제설명

입출력

풀이

일단 문제는 비교적 간단합니다.
펭귄이 있는 위치를 기준으로 왼쪽의 최소값과 오른쪽의 최소값을 구하면 되는 문제입니다.

처음에 생각하지 않고 바로 적용했던 풀이는 먼저 펭귄의 위치를 찾고 해당 위치를 기준으로 왼쪽, 오른쪽 최소값을 찾는 방법입니다.
이렇게 하면 중첩되진 않더라도 총 4개의 for문이 나오더라구요.
오답처리 됐네요.. ㅎ

문제가 간단한 만큼 충분한 고민을 해야 합니다..

한 번의 for문으로 풀이가 가능합니다.
우선순위 큐를 이용하는 풀이입니다.

• 펭귄이 있는 위치(L)이 발견될 때까지 pq에 삽입합니다. (min-heap)
• 펭귄이 발견되면 지금까지 누적된 pq의 root를 꺼냅니다 (poll)
  이때 꺼낸 값이 펭귄 기준 왼쪽의 최소값 입니다.
  꺼낸 값을 변수에 저장합니다.
• pq를 초기화(clear)하고 다시 끝까지 값을 pq에 삽입합니다.
• 모든 반복이 끝나면 pq의 루트노드가 펭귄기준 오른쪽의 최소값이 됩니다.
• 오른쪽 최소값까지 누적시켜주고 정답을 리턴합니다.

Java Code

package com.example.boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * https://www.acmicpc.net/problem/18228
 * 펭귄추락대책위원회
 */

public class Q18228_2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        int res = 0;
        Queue<Integer> pq = new PriorityQueue<>();
        for (int i=0;i<n;i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (cur == -1) {
                res += pq.poll();
                pq.clear();
                continue;
            }
            pq.offer(cur);
        }
        System.out.println(res+pq.poll());
    }
}