[BOJ] 6198번 옥상정원 꾸미기

개요

배열을 이용해서 해결할 수 있지만 스택을 이용하면 시간복잡도가 많이 줄어드는 문제

문제링크

배열을 이용한 코드

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

public class Baekjoon6198 {
	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());
        long[] b = new long[n];
		
        for(int i=0;i<n;i++)
        	b[i] = Long.parseLong(br.readLine());

        long hight = 0;
        long count = 0;
        for(int i=0;i<n;i++) {
        	hight = b[i];
        	for(int j=i+1;j<n;j++) {
        		if(b[j]>=hight) 
        			break;
        		count++;
        	}
        }
        bw.write(count+"\n");
        bw.flush();
        br.close();
        bw.close();
	}
}

스택을 이용한 코드

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

public class Baekjoon6198 {
    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());
        long[] b = new long[n];
        Stack<Long> s = new Stack<>();

        for(int i=0;i<n;i++)
            b[i] = Long.parseLong(br.readLine());

        long hight;
        long count = 0;
        for(int i=0;i<n;i++) {
            hight = b[i];
            while(!s.isEmpty() && s.peek() <= hight)    //s.peek > hight
                s.pop();

            count += s.size();
            s.push(hight);

        }
        bw.write(count+"\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

해결 과정

배열을 이용할 때는 문제에서 예시를 들었던 방식을 그대로 구현하면 된다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

하지만 스택을 이용하여 문제를 해결할 때는 보는 관점을 바꿔야 하는데

배열은 관리인의 관점에서 보았다면 스택은 빌딩의 관점에서 보아야한다.

• 1번 빌딩의 옥상을 확인할 수 있는 관리인은 없다.
• 2번 빌딩의 옥상을 확인할 수 있는 관리인은 1번
• 3번 빌딩의 옥상을 확인할 수 있는 관리인은 1번
• 4번 빌딩의 옥상을 확인할 수 있는 관리인은 1, 3번
• 5번 빌딩의 옥상을 확인할 수 있는 관리인은 없다
• 6번 빌딩의 옥상을 확인할 수 있는 관리인은 5번

따라서, 총 수는 0 + 1 + 1 + 2 + 0 + 1 = 5이다.

배열 결과

스택 결과