[백준] 6198 옥상 정원 꾸미기 / 자바(Java)

문제

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

---

해설

각 빌딩별 오른쪽에 있는 자신보다 크거나 같은 빌딩과의 사이에 있는 빌딩의 수들의 합을 구하는 문제입니다.

각 빌딩별로 오른쪽을 탐색하면 확인하는 과정을 거친다면 O(n^2)의 시간복잡도를 가져 시간초과가 날 수 있습니다.

 

발상의 전환으로 각 빌딩별 자신을 볼 수 있는 빌딩의 수를 구한다면? 각 빌딩기준 왼쪽에 자신보다 큰 빌딩의 수를 구한다면 O(n)으로 해결이 가능하다 생각되어 그런 방향으로 문제를 해결하려 합니다.

 

이를 구현하기 위해 스택을 사용합니다. 스택의 peek를 통해 가장 위에 있는 높이를 확인하여 새로 들어오는 높이보다

크다면 스택 내부의 모든 빌딩들이 자신을 볼 수 있는 것이고,

높이가 작다면 이전의 peek를 제거하는 것

( peek를 제거하고 새로 들어오는 빌딩의 높이가 들어가면 제거된 빌딩은 지금 들어온 빌딩에 의해 앞으로 들어올 빌딩을 볼 수 없으므로 영향이 없어집니다.)

을 반복하여 스택을 통해 자신을 볼 수 있는 빌딩의 수를 구할 수 있습니다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

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

        int N = Integer.parseInt(br.readLine());

        Stack<Long> s1 = new Stack<>();

        long ans = 0;

        // 새로 들어온 빌딩들 기준으로 내 빌딩이 보이는 곳의 수만큼씩 더해준다.
        for (int i = 0; i < N; i++) {
            long tmp = Long.parseLong(br.readLine());
            // tmp >= s1.peek() ==> 기존의 스택에 있던 빌딩중 나보다 더 작은 빌딩들 삭제(앞으로도 추가될 여지가 없다)
            while(!s1.isEmpty() && tmp >= s1.peek()){
                s1.pop();
            }
            s1.push(tmp);

            ans += s1.size()-1;
        }



        System.out.println(ans);
    }
}