BOJ_6198_옥상 정원 꾸미기 JAVA 풀이

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

해당 문제는 시간복잡도 O(N)에 풀어야 하는 문제다.

문제 이해는 빨랐으나, 어떤식으로 구현해야할지 생각을 좀 했고,
O(N^2)로 풀이한다면 굉장히 쉬운 풀이 방법이 되겠지만,
N^2은 64억이므로 시간초과가 무조건 난다.

내가 처음 생각한 방법은
1. 빌딩을 스택에 넣으며
2. stack.peek() 가 현재 arr[index]보다 크면
3. stack.push(arr[index]) 하며
4. 그렇지 않다면 stack.peek() 가 현재 arr[index] 보다 클 때까지 계속 pop()한다.
5. 해당 빌딩은 스택에 넣어주며,
6. 해당 빌딩을 바라볼 수 있는 빌딩들의 갯수를 answer에 누적시킨다.

예제:

6
10
3
7
4
12
2

순서는,
1. 10
2. 10 3
3. 10 7
4. 10 7 4
5. 12
6. 12 2
순으로 계산하면 될 것이다.

1. 처음 코드

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

public class Main {

    public int solution(int[] arr, int n){
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++){
            if (stack.isEmpty()) stack.push(i);
            else {
                if (arr[stack.peek()] > arr[i]){
                    stack.push(i);
                }else {
                    // stack 의 top 이 현재 빌딩보다 커지거나 같아질 때까지 스택 팝
                    while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]){
                        stack.pop();
                    }
                    stack.push(i);
                }
            }
            // 현재 i 에서 볼 수 있는 경비원 파악
            // 스택의 size - 1을 할 것임.

            answer += stack.size() - 1;
        }

        return answer;
    }

    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());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(new Main().solution(arr, n));

    }
}

-> 분명히 내가 생각한 로직이 맞는데 안된다.. 그래서 찾아봤더니 문제를 다시 천천히 읽어보니...
-> N이 80000이므로 최악의 경우 누적 합이 79999 + 79998 + 79997 ..... = 3199960000 이었던 것이다.. int type은 overflow가 발생한다.
-> 그래서 누적시키는 answer 변수를 long 형으로 바꿨다.

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

public class BOJ_6198_옥상꾸미기 {

    public long solution(int[] arr, int n){
        long answer = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++){
            while (!stack.isEmpty() && stack.peek() <= arr[i]){
                stack.pop();
            }
            stack.push(arr[i]);
            // 현재 i 에서 볼 수 있는 경비원 파악
            // 스택의 size - 1을 할 것임.
            answer += stack.size() - 1;
        }

        return answer;
    }

    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());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(new BOJ_6198_옥상꾸미기().solution(arr, n));
    }
}

• 리팩토링 적용 및 answer 변수 long형으로 수정