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

💡 접근 방법 순서

1. N이 50,000보다 작거나 같고 이외의 높이 조건 (500,000 이하)를 봤을 때$O(N^2)$ 풀이가 불가능 하기 때문에 $O(N)$ 또는 $O(NlogN)$ 풀이를 생각하며 시작한다.
2. 주어진 데이터는 빌딩 왼쪽부터 위치 순서대로 나오기 때문에 먼저 가장 쉽게 위치 순서대로 빌딩 높이를 보며 풀이 방법을 생각해본다.
3. 풀다 보면 n번째 위치의 빌딩을 볼 때 문제에서 원하는 최소 빌딩 개수를 알 수 있다는 사실을 발견할 수 있다.

예시)

• input

3
1 2
2 4
3 3
4 2

• result

x	최소 빌딩 개수
1	1
2	2
3	3
4	3

4. 3번을 재해석 하면 특정 위치에서의 답은 미래의 input과 상관 없이 정해진다는 것을 의미한다.

✒️ 풀이 특징 분석

1. 건물 높이가 똑같이 주어진다고 하더라도 다음 건물 위치에서 정답 count가 추가될지 안될지는 이전 히스토리에 따라 다르다.
2. 다음의 예시를 생각해보자.
   예시)

• input

5
1 2 // 1번
2 4 // 2번
3 2 // 3번
4 1 // 4번
5 2 // 5번

1번, 3번, 5번은 모두 같은 건물 높이를 가지고 있다.
1번 input이 3번과 5번에 미치는 영향을 알아보자. 1번이 3번과 5번 모두에게 영향을 미칠까? 하나만 미칠까? 아니면 전혀 영향이 없을까?

3. 3번에는 영향을 미치지만 5번은 영향을 미치지 않는다. 조금만 더 확장 시켜보면 4번 이후로 나오는 모든 건물들은 1번 input에 영향을 받지 않는다. 즉 특정 데이터는 특정 시점 이후로 삭제되어도 무방하다는 것을 의미한다.

4. 특정 시점 이후로 삭제되어도 무방하다는 것을 다른 관점으로 해석해보면 상대적으로 최근의 데이터가 현재 시점의 정답을 결정하는데 영향을 미친다고 생각해볼 수 있다.

✨ 결론

Stack 을 시도해보자.

• stack은 각 데이터를 한번 씩만 넣고 뺀다고 했을 때 $O(N)$ 풀이가 보장된다.
• stack은 히스토리를 저장할 수 있다.
• 최근의 데이터를 사용하기 때문에 LIFO 구조인 stack 풀이 방법에 좀 더 가능성을 둘 수 있다.

📜 Solution

다행이 stack으로 풀렸다!

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    static Counter counter;
    static int N;

    static class Counter {
        Deque<Integer> stack;
        int cnt;

        public Counter() {
            stack = new ArrayDeque<>();
            cnt = 0;
        }

        public void add(int height) {
            // 만약 stack의 탑보다 더 크다면 추가
            if (stack.isEmpty() || height > top()) {
                if(height == 0) return;
                stack.addLast(height);
            } else if (height < top()) {
                // 작다면 top이 더 작아질 때까지 빼낸다.
                while (!stack.isEmpty() && height < top()) {
                    int h = stack.pollLast();
                    cnt++;
                }
                add(height);
            }
        }

        private int top() {
            return stack.peekLast();
        }

        public int total() {
            return cnt + stack.size();
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        counter = new Counter();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            counter.add(Integer.parseInt(st.nextToken()));
        }

        sb.append(counter.total());

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

🤔 생각해본 다른 풀이

boolean 배열을 사용한 히스토리 기록

• 구현 방법에 따라 될 수도 있겠지만 단순하게 생각해보았을 때 높이 100에서 높이 1인 빌딩이 나오는 경우 높이 2~100의 모든 빌딩들을 선형적으로 수정해야 하므로 N과 H의 범위를 생각해볼 때 시간초과가 날 가능성이 크다.