6198 - 옥상 정원 꾸미기 (Java)

 

---

 

문제

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

 

 

풀이

스택을 활용해야 하는 문제이다.

 

N이 8만이므로, 완탐은 당연히 안된다.

 

앞에서부터 스택에 데이터를 넣는데, 이때 빌딩번호와 높이를 같이 넣는다.

다음 빌딩이 스택의 가장 위의 빌딩보다 낮으면 그냥 넣어준다.

 

만약 다음 빌딩이 만약 더 크다면?

 

스택에서 빼서, 빌딩 번호의 차를 구하고 답에 더해주면 된다.

 

스택에서 빼는 과정을 자신보다 낮은 빌딩이 나올때까지 반복하면 된다.

 

그렇게 끝까지 반복적으로 수행한다음에, 스택에 남아있다면

 

남아있는 빌딩들은 오른쪽 끝까지 볼 수 있는 빌딩이므로 값을 계산해서 답에 추가해주면 된다.

 

코드

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

/**
 * [문제] (https://www.acmicpc.net/problem/6198)
 */

public class Main {

    public static Integer n;
    public static List<Integer> heights = new ArrayList<>();
    public static Stack<Building> stack = new Stack<>();
    public static Long answer = 0L;

    public class Building {
        public Integer number;
        public Integer height;

        public Building(Integer number, Integer height) {
            this.number = number;
            this.height = height;
        }
    }

    public void solution() throws Exception {
        inputProcess();

        for (int i = 0; i < heights.size(); i++) {
            Building currentBuilding = new Building(i, heights.get(i));

            // 들어오는 빌딩이 더 높다면 낮은 값이 나올때 까지 또는 빌때까지 빼고 계산한다.
            while(!stack.empty() && stack.peek().height <= currentBuilding.height){
                Building recentBuilding = stack.pop();
                answer += (currentBuilding.number - recentBuilding.number - 1);
            }
            stack.push(currentBuilding);
        }

        while (!stack.empty()) {
            answer += (n - stack.pop().number - 1);
        }

        System.out.println(answer);
    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void inputProcess() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            heights.add(Integer.parseInt(br.readLine()));
        }
    }

}

 

후기

 

- 크거나 같으면 못 본다는 조건을 캐치하지 못하고 큰 값만 체크했다가 틀렸다.

 

- 정답이 Integer 범위를 넘을 수 있을거라는 부분을 캐치하지 못함,,