[Baekjoon Online Judge] 백준 6198번 옥상 정원 꾸미기(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 6198번 옥상 정원 꾸미기

(Python)

(글쓴날 : 2020.05.13)

 

---

* Baekjoon Online Judge, 백준 6198번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 6198번 옥상 정원 꾸미기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

높이가 각각 다른 N개의 빌딩이 주어지고 왼쪽에서 오른쪽으로 자신보다 낮은 빌딩들의 옥상을 확인할 수 있을 때, 각 빌딩별로 다른 옥상을 확인할 수 있는 경우의 수의 합을 구하는 문제입니다.

단, 왼쪽에서 오른쪽으로 다른 빌딩들을 확인하다 더 높은 빌딩이 나왔을 경우 그 이후의 빌딩은 높이에 상관없이 확인할 수 없습니다.

 

저의 경우, 스택을 이용하였고, Python을 사용했습니다.

다른 빌딩을 확인할 수 있는 반대 방향으로(오른쪽에서 왼쪽으로) 탐색을 시작하여 스택을 이용해 만약 스택이 비었을 경우 현재 빌딩에서 볼 수 있는 빌딩의 수와 높이를 튜플로 저장하였고 스택에 빌딩이 있을 경우 현재 빌딩보다 높이가 낮을 시 스택에서 꺼내 해당 빌딩이 볼 수 있는 빌딩의 수를 구했으며, 만약 현재 빌딩보다 높을 시엔 스택이 비었을 때처럼 현재 빌딩의 정보를 스택에 저장하는 식으로 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
h = [int(input()) for _ in range(N)]
stack = []
ans = 0
 
for i in range(N - 1, -1, -1):
    seeable = 0
    while(True):
        if not len(stack):
            stack.append((0, h[i]))
            break
 
        if stack[-1][1] < h[i]:
            seeable += stack.pop()[0] + 1
 
            while(True):
                if not len(stack):
                    stack.append((seeable, h[i]))
                    ans += seeable
                    break
                if stack[-1][1] < h[i]:
                    seeable += stack.pop()[0] + 1
                else:
                    stack.append((seeable, h[i]))
                    ans += seeable
                    break
 
            break
        else:
            stack.append((0, h[i]))
            break
 
print(ans)

---