자바 - 코드트리 / 빙산의 일각

https://www.codetree.ai/training-field/search/problems/the-tip-of-the-iceberg?&utm_source=clipboard&utm_medium=text

실버1

구현 방법

실버1이라고 만만하게 봤다가 된통 당한 문제!

input 데이터 범위를 보면 아래와 같기 때문에 O(n)으로 해결해야 한다.

빙산들의 개수 N, 빙산의 높이 H(i)

• 1 ≤ N ≤ 100,000
• 1 ≤ H(i) ≤ 1,000,000,000

처음에는 높이를 기준으로 매개변수 탐색을 진행 해서 O(nlogn)으로 풀려고 호기롭게 도전했으나,

무수히 많은 예외 케이스들이 존재했다. 

다시 생각해보면 높이 자체와 빙산의 개수는 아무런 연관관계가 없기 때문에 아주 잘못된 접근임을 깨닮았다.

그럼 빙산의 개수는 어떤것과 연관이 있을지 고민했다.

잘 생각해보면 빙산의 개수는 주변의 빙산들의 높이와 연관되어 있다. 

예를 들어, 현재 빙산 기준 좌우에 빙산이 존재하면 이건 한덩어리가 되는 것이다.

 

이를 바탕으로 로직을 구현하면 된다. (여기서 구현 로직까지 생각하는게 되게 오래 걸렸다.)

 

구현 순서

1. 빙산의 높이가 높은 순부터 차례로 주변을 탐색한다. 그 후 현재 높이 기준 좌, 우를 방문한 적이 없다면 빙산 덩어리 개수를 하나 추가한다.

 

2. 만약 좌 우 둘다 방문한 적이 있다면, 이는 현재 높이보다 높은 빙산에 덩어리가 합쳐지는 것이므로 빙산 덩어리 개수를 하나 줄인다.

예를 들어 323 높이로 빙산을 이루고 있다면, 앞서 양쪽에 3에서 각각의 덩어리가 생겼을 것이다. 그후 2높이에서는 양쪽 덩어리들과 ㅎ합쳐지기 때문에 2개의 덩어리가 1개의 덩어리로 바뀌게 된다.

 

3. 이제 최대 빙산 덩어리 개수를 구해야한다. 이는 현재까지의 빙산 덩어리의 개수와 지금까지의 최대값을 비교하여 갱신한다. 

이 때 주의해야 할 점은 현재 빙산 높이와 다음 빙산 높이가 같은 경우에는 갱신하면 안된다. 만약 112 처럼 같은 높이가 연속적으로 있다면 112는 높이 1에서 한 덩어리가 되어야 하는데, 첫번째 1만 처리한다면 두 덩어리가 되기 때문이다.

(3번를 고려하지 않고 코드 작성해서 틀렸다.)

코드

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

/**
* 코드트리
* 빙산의 일각
* 실버1
* https://www.codetree.ai/training-field/search/problems/the-tip-of-the-iceberg?&utm_source=clipboard&utm_medium=text
*/
public class 빙산의일각 {
    private static class Node implements Comparable<Node> {
        int index;
        long h;

        Node(int index, long h) {
            this.index = index;
            this.h = h;
        }

        @Override
        public int compareTo(Node o) {
            return Long.compare(o.h, h);
        }
    }

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

        int N = Integer.parseInt(br.readLine());
        long[] heights = new long[N + 2];

        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 1; i <= N; i++) {
            heights[i] = Long.parseLong(br.readLine());
            pq.add(new Node(i, heights[i]));
        }

        boolean[] visited = new boolean[N + 2];
        long answer = 0;
        long cnt = 0;
        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            if(!visited[cur.index - 1] && !visited[cur.index + 1]) {
                cnt++;
            } else if(visited[cur.index - 1] && visited[cur.index + 1]) {
                cnt--;
            }

            visited[cur.index] = true;

            if(pq.isEmpty() || pq.peek().h != cur.h){
                answer = Math.max(answer, cnt);
            }
        }

        System.out.println(answer);

    }
}