[Baekjoon] 6198_옥상 정원 꾸미기

Gold V

문제(출처: https://www.acmicpc.net/problem/6198)

---

<옥상 정원 꾸미기>

문제 

 

도시에는 N개의 빌딩이 있다.
빌딩 관리인들은 매우 성실하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹하고 싶어 한다.
i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.
i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2,.... , N이다.
그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그다음에 있는 모든 빌딩의 옥상은 보지 못한다.
예) 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이다.

 

 

입력

 

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

 

출력 

 

각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

 

 

문제 풀이

-  초기 코드: 시간 초과

if __name__=='__main__':
    n=int(input())

    stack=[]
    answer=0

    for i in range(n):
        h=int(input())
        stack.append(h)

    for i in range(n):
        for j in range(i+1,n):
            if stack[i]>stack[j]:
                answer+=1
            else:
                break
    print(answer)

 

문제가 원하는 것이 stack인지 알고 있었지만 이중 for문으로 가능하지 않나 생각하여 풀었다가 바로 시간 초과 발생한 코드

 

사실 바로 stack으로 풀고 싶었는데 풀 방법이 생각 안 나서 한참 생각했다.

생각하다 생각하다 결국 검색의 힘을 빌렸다.

 

생각하는 관점을 바꾸자 -!

현재 건물에서 볼 수 있는 건물의 수를 세는 것이 아니라 자신을 볼 수 있는 건물을 세는 방법이었다.

 

 

 - my solution (Python)

if __name__=='__main__':
    n=int(input())

    arr=[]
    answer=0

    for i in range(n): # 빌딩 높이
        h=int(input())
        arr.append(h)

    stack=[]
    for i in range(n):
        while stack:
            if stack[-1]<=arr[i]: # 자신의 빌딩 높이보다 낮다면
                stack.pop()
            else:
                break
        stack.append(arr[i])
        answer+=len(stack)-1

    print(answer)

 

 

- my solution (JAVA)

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

public class _6198_옥상정원꾸미기 {

	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];
		long answer=0;
		
		for(int i=0; i<n; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		
		Stack<Integer> stack=new Stack<>();
		for(int i=0; i<n; i++) {
			while(stack.size()!=0) {
				if(stack.peek()<=arr[i]) {
					stack.pop();
				}else {
					break;
				}
			}
			stack.add(arr[i]);
			answer+=stack.size()-1;
		}
		System.out.println(answer);
	}
}

 

• 빌딩의 수, 빌딩의 높이 입력
• 빌딩을 순환
  : stack에 값이 있다면
  -> 현재 빌딩의 높이가 stack에 있는 마지막 빌딩의 높이보다 높다면
   = stack에 있는 빌딩은 현재 빌딩을 볼 수 없으므로 stack에서 pop
  : stack에 현재 빌딩을 추가
  : stack에는 현재 빌딩을 제외한 자신을 볼 수 있는 빌딩들이 존재하므로 stack의 길이 -1을 answer에 더함
• answer 출력

 

 

❓ JAVA에서 왜 틀렸습니다가 발생했는가?

파이썬과 로직이 같은데 왜 틀렸나 해서 찾아보니... 답이 int형을 넘어갈 수 있어 발생한 문제였다.

파이썬에서는 고려하지 않았던 부분... answer을 long형으로 바꿔서 제출하니 통과할 수 있었다.

 

 

---

생각🤔

 

이 문제는 검색을 통해서도 이해하기 힘들어 한참 생각한 문제였다.

그래도 결국 이해하긴 했지만 깔끔하지는 않았던 것 같다.

 

---