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

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

6198번: 옥상 정원 꾸미기

 

<문제 분석>

i번째 건물에서 볼 수 있는 건물의 수를 구해야 한다. 이중 루프를 돌려서 i번째 건물보다 작은 건물이 나오면 sum++를 해주면 되는데... 순차검색으로 풀면 타임 아웃이 발생한다.

문제는 N <= 80,000이라서 건물의 수가 8만개인데 첫 빌딩이 제일 높고 차례대로 낮을 경우 경우의 수가 8만개의 제곱(64억회)에 육박하게 된다. 따라서 시간 복잡도 O(N^2)를 줄일 수 있는 다른 방법을 찾아야 한다.

 

이 문제는 스택을 사용해서 푸는 대표적인 문제인데, 스택에 어떤 값을 저장하고 어떤 값을 제거할 지 기준을 정해야 한다.

그런데, i번째 빌딩에서 보이는 건물을 스택에 넣는다면 for문의 진행방향에 있는 건물들을 스택에 넣어야 하는데 그 스택의 값이 다음 i번째 건물과 중복되게 된다.

 

이 문제를 풀려면 문제를 재정의 해야 한다.

'i번째 건물에서 보이는 다른 건물의 수'가 아니라 'i번째 건물을 볼 수 있는 다른 건물의 수'를 구하면 된다.

 

(증명)
* i번째 건물이 볼수 있는 건물의 수
(1) 3개: 1->2, 1->3, 1->4
(2) 0개
(3) 1개: 3->4
(4) 0개
(5) 1개: 5->6
(6) 0개

* i번째 건물을 볼수 있는 건물의 수
(1) 0개
(2) 1개: 1->2
(3) 1개: 1->3
(4) 1개: 3->4, 1->4
(5) 0개:
(6) 1개: 5->6

 

즉, 카운트 되는 위치만 달라졌을 뿐 실제 빌딩의 번호와 수는 동일함을 알 수 있다.

이 문제를 기준으로 코드를 구현해보면 아래와 같다.

 

<풀이>
1. 스택에 1번 건물을 삽입한다.
2. for 루프를 돌린다. (0 to N)
3. stack이 빈게 아니면 i번째 빌딩과 비교한다.
  3-1. stack의 저장된 빌딩의 높이가 i번째 빌딩의 높이와 같거나 작으면 제거한다.
  3-2. stack에 저장된 빌딩은 다 비교해야 한다.
  3-3. 비교를 다해도 stack에 값이 남아 있을 수 있기 때문에 while(!stack.isEmpty())를 단독으로 쓰면 무한루프에 걸린다.
      while(!stack.isEmpty() && stack.peek() <= H[i])를 사용해야 한다.
4. stack의 빌딩을 다 비교하면 남아있는 빌딩의 수는 i번째 빌딩을 볼 수 있는 건물의 수이다. sum += count 한다.

<코드 구현>

import java.util.Scanner;
import java.util.Stack;

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

public class Main {
	static int N;
    static int H[];

	public void InputData()
	{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
        H = new int[N+1];
		for (int i = 1; i <=N; i++) // 건물번호를 1번 to N
		{
			H[i] = sc.nextInt();
		}
		sc.close();
	}
	
	public void Solve() {
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        // i번째 건물을 볼수 있는 건물의 수 구하기 (높이가 더 큰 건물만 스택 삽입)
        for (int i=1; i<=N; i++) {
            // 스택에 있는 건물과 i번째 건물의 높이 비교
            while (!stack.isEmpty() && stack.peek() <= H[i]) {
                // 스택의 건물이 i건물과 높이가 같거나 작으면 삭제
                stack.pop(); // 제거 후 다음 건물도 비교
            }
            // i번째 건물을 볼 수 있는(큰) 건물의 수
            sum += stack.size();
            stack.push(H[i]);
        }
        System.out.println(sum);
	}
    
	public static void main(String[] args) 
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<결과 제출>

 

<결과 분석>

타임 아웃도 아니고 결과가 틀렸다고 나와서 코드를 다시 살펴보니 변수의 단위가 부족한 것을 발견했다.

N^2가 시간 복잡도 뿐만 아니라 변수의 크기도 64억이 나올 수 있기 때문에 int sum -> long sum으로 변경해 주었다.

 

<2차 구현>

import java.util.Scanner;
import java.util.Stack;

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

public class Main {
	static int N;
    static int H[];

	public void InputData()
	{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
        H = new int[N+1];
		for (int i = 1; i <=N; i++) // 건물번호를 1번 to N
		{
			H[i] = sc.nextInt();
		}
		sc.close();
	}
	
	public void Solve() {
        Stack<Integer> stack = new Stack<>();
        long sum = 0;
        // i번째 건물을 볼수 있는 건물의 수 구하기 (높이가 더 큰 건물만 스택 삽입)
        for (int i=1; i<=N; i++) {
            // 스택에 있는 건물과 i번째 건물의 높이 비교
            while (!stack.isEmpty() && stack.peek() <= H[i]) {
                // 스택의 건물이 i건물과 높이가 같거나 작으면 삭제
                stack.pop(); // 제거 후 다음 건물도 비교
            }
            // i번째 건물을 볼 수 있는(큰) 건물의 수
            sum += stack.size();
            stack.push(H[i]);
        }
        System.out.println(sum);
	}
    
	public static void main(String[] args) 
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출 결과>