[백준] 6198번 옥상 정원 꾸미기 - Java, 자바

난이도

골드 5

문제

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

풀이

틀린코드

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


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

        int n  = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i]= Integer.parseInt(br.readLine());
        }

        int count=0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(arr[i]<=arr[j]){
                    break;
                }
                count++;
                //System.out.println(arr[i]+" "+arr[j]);
            }

        }

        System.out.println(count);
    }
}

위의 풀이는 이중반복문으로 문제를 해결했는데 시간 초과가 났다.

그 이유는 N^2은 64억이므로 시간초과가 난다.

시간초과가 나는 이유

https://yaneodoo2.tistory.com/41
현재 주어진 N의 범위는 80000인데, 위의 글을 참고하면 N의 범위가 2000을 넘기므로 N^2으로 짜면 시간초과가 나므로 다른 방법을 고안해야함을 알 수 있다.

또한, 빌딩이 모두 내림차순일 때 가능한 빌딩수의 합은
79999+79998+... = (80000)*(80001)/2 = 3200040000 = 32억을 넘으므로 result를 long으로 바꿔야한다

스택 문제 풀이

이 문제는 알고리즘을 분류를 보면 스택으로 되어있으므로 스택으로 풀어야함을 알 수 있다.

1. 이전에 위치한 빌딩 중 새로운 빌딩의 높이보다 낮은 빌딩은 모두 제거
2. 새로운 빌딩을 추가
3. 스택에 남아있는 빌딩은 새로운 빌딩보다 높으므로(스택안은 내림차순을 유지) 해당 사이즈 -1만큼 회수를 카운트

i=0 | tmp=10 | statck=[10] | res=0 | s.size()-1=0
i=1 | tmp=3 | statck=[10,3] | res=1 | s.size()-1=1
i=2 | tmp=7 | statck=[10,7] |res=2 | s.size()-1=1
i=3 | tmp=4 | statck=[10,7,4] | res=4 | s.size()-1=2 <- 10은 4보다 크므로+1, 7은 4보다 크므로 +1
i=4 | tmp=12 | statck=[12] | res=4 | s.size()-1=0
i=4 | tmp=2 | statck=[12,2] | res=5 | s.size()-1=1

코드

package 기타;

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

public class BOJ6198 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long result = 0;
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < n; i++) {
            int tmp = Integer.parseInt(br.readLine());
            while (!s.isEmpty() && s.peek() <= tmp) {
                s.pop();
            }
            s.push(tmp);
//            System.out.println(s.size()-1);
            result += s.size() - 1;

        }

        System.out.println(result);

    }
}

https://loosie.tistory.com/747##6198_%EC%98%A5%EC%83%81_%EC%A0%95%EC%9B%90_%EA%BE%B8%EB%AF%B8%EA%B8%B0
https://velog.io/@xonic789/BOJ6198%EC%98%A5%EC%83%81-%EC%A0%95%EC%9B%90-%EA%BE%B8%EB%AF%B8%EA%B8%B0-JAVA-%ED%92%80%EC%9D%B4