[백준 6198번: 옥상 정원 꾸미기](Java)

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

6198번: 옥상 정원 꾸미기

 

알고리즘 분류 : Monotone Stack

 

문제를 읽고, 어떤 방식으로 구현해봐야 하는지에 대해 생각해보았다. 처음 생각해낸 방법은 브루트 포스 방식이었다.

Array로 빌딩의 높이 값을 모두 입력 받은 다음, N만큼 반복문을 돌면서 현재 빌딩 높이와 비교하는 로직을 구하는 것이었다. 그러나 이 방법에 대해 마음에 들지 않는 두 가지 포인트가 있었다.

 

1. 시간복잡도가 O(n^2)이라는 것

첫 번째 빌딩은 n-1 개의 빌딩과 비교해야 하고, 두 번째는 n-2, 계속해서 n-3... 1까지.

이렇게 되면 대략 n^2 / 2 만큼의 연산을 해야 한다.

 

2. 분기 처리의 복잡성

단순히 빌딩의 높낮이만으로 이 문제를 풀 수 있는 것이 아니다. 아무리 낮은 빌딩이라도, 그 앞에 현재 빌딩 보다도 더 큰 빌딩이 있다면, 뒤에 있는 낮은 빌딩의 옥상은 볼 수 없다.

 

이러한 이유로 더 효율적인 방식이 있을 것이라는 직감이 들었고, 뾰족한 방법이 도무지 생각나지 않아서 해당 문제의 풀이에 대해 검색을 해보았다. 4번째 글 즈음에서 'Monotone Stack'이라는 자료구조를 활용하면 된다는 내용을 발견했고 이에 대해 공부해 보았다.

 

Monotone Stack 은 Stack 내부의 값을 오름차순 혹은 내림차순으로 정렬한 상태로 유지하는 알고리즘이다.

해당 자료구조의 장점은 아래와 같다.

 

Using monotonic stack to maintain a range can save lots of time. Because it only updates information within the range based on new adding elements and avoids repetitive operations of existing elements. To be more precisely, the monotonic stack helps us maintain maximum and and minimum elements in the range and keeps the order of elements in the range. Therefore, we don’t need to compare elements one by one again to get minima and maxima in the range. At mean while, because it keeps the elements’ order, we only need to update the stack based on newest adding element.

 

출처 : https://medium.com/techtofreedom/algorithms-for-interview-2-monotonic-stack-462251689da8 

Algorithms for Interview 2: Monotonic Stack

 

 

찾아봤던 자료에 위와 같은 글이 있었다. 새롭게 데이터가 추가되면, 그 전의 범위 내에서만 연산이 일어나며, 그다음 추가된 데이터에서 해당 값들을 기반으로 stack을 update 시키므로, 시간 복잡도를 O(N)으로 줄일 수 있다는 사실을 알게 되었다. Monotone Stack의 작동 원리는 아래 링크를 참고했다.

https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/

monotone stack

 

이제 본격적으로 문제풀이와 관련해 이야기해보겠다.

 

1. PS를 위한 Data Structure은 Monotone Stack을 활용할 것

Monotone Stack을 내림차순 하여 사용하면, N 번째 빌딩을 검사할 때, N-1까지의 빌딩들 중에서 N 번째 빌딩보다 큰 빌딩들만 남게 된다. 이는 N 번째 빌딩을 볼 수 있는 빌딩들이 되는 것이기 때문에, stack의 size는 N 번째 빌딩을 볼 수 있는 다른 빌딩의 수가 되는 것이다.

 

2. 부가적인 변수들의 자료구조 확인

PS를 할 때 설계해야 하는 부분에는 입출력 값을 담을 변수들에 대한 자료구조가 필수적으로 포함된다. 이번 문제의 입력값 조건은 아래와 같다.

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

int type의 경우에는 MAX_VALUE가 2,xxx,xxx,xxx 어쩌구인것으로 기억한다. (2,147,483,647)

언듯 보기에는 int type을 이용해도 문제가 없을 것 같아 보이지만, 우리가 답으로 제출해야 하는 벤치마킹이 가능한 빌딩의 수의 합에 대해 생각해보자.(이하 sum)

 

sum 변수가 가지게 되는 최대 값의 상황을 생각해보자.

80,000개의 빌딩 데이터가 주어지고, 첫 번째 빌딩이 79,999개의 빌딩을 볼 수 있다고 생각해보자. 그리고 그다음 빌딩들은 순서대로 79_998, 79_997... 2, 1, 0 개의 빌딩을 벤치마킹할 수 있을 것이다.

그럴 경우 80,000 * (79999 + 0 ) / 2 가 sum의 최종 값이 될 것이다.

 

괄호 안의 값을 대략 80000이라고 가정하고 암산해보면 sum의 값은 대략 3,200,000,000이 도출된다.

 

자료형	MAX_VALUE
우리가 담아야 하는 최대 데이터	3,200,000,000 (정확히는 3,199,960,000)
int	2,xxx,xxx,xxx   (정확히는 2,147,483,647)
unsigned int	4,xxx,xxx,xxx (int의 2배일테니까!, 정확히는 4,294,967,295)
long	9,223,372,036,854,775,807

 

위 표를 보고 판단한다면, int는 어림도 없다. unsigned int는 JAVA에서는 지원하지 않는다. 따라서 우리는 long type으로 sum 변수를 선언해야 함을 알 수 있다.

 

 

 

[정답 코드] 

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()), input;
        long sum = 0;
        Stack<Integer> s = new Stack<>();

        for (int i = 0; i < N; i++) {
            input = Integer.parseInt(br.readLine());
            while (!s.empty()) {
                if (s.peek() > input) break;
                s.pop();
            }
            sum += s.size();
            s.push(input);
        }
        bw.write(String.valueOf(sum));
        bw.flush();
    }
}