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

문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

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

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 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)

출력

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

내가 쓴 코드 1 (틀림)

# for문으로
from sys import stdin; input = stdin.readline
N = int(input())
buildings = []
for _ in range(N):
    buildings.append(int(input()))

# -> 이 방향으로 바라봄
# 자기보다 낮은 빌딩만 볼 수 있음

num = []
for i in range(N):
    cnt = 0
    for j in range(i + 1, N):
        if buildings[i] > buildings[j]:
            cnt += 1
        else:
            break
    num.append(cnt)
print(sum(num))
# 4% -> 시간초과

# while문으로
from sys import stdin; input = stdin.readline
N = int(input())
buildings = []
for _ in range(N):
    buildings.append(int(input()))

# -> 이 방향으로 바라봄
# 자기보다 낮은 빌딩만 볼 수 있음

i = 0
low = []
while i < N:
    cnt = 0
    for j in range(i + 1, N):
        if buildings[i] > buildings[j]:
            cnt += 1
        else:
            break
    low.append(cnt)
    i += 1
print(sum(low))
# 4% -> 시간초과

 

내가 쓴 코드 2 (맞.)

from sys import stdin; input = stdin.readline
N = int(input())

# -> 이 방향으로 바라봄
# 자기보다 낮은 빌딩만 볼 수 있음

cnt = 0
stack = []  # 오른쪽 빌딩 중 자신보다 작은 빌딩들
for _ in range(N):
    building = int(input())
    # building보다 큰 빌딩들은 stack에서 pop
    while stack and building >= stack[-1]:
        stack.pop()
    cnt += len(stack)   # building보다 작은 빌딩들 수의 합
    stack.append(building)
print(cnt)

진짜 이해하기 힘든 로직이었다... 어떻게 발상을 반대로 바꿔서..... 생각할 수 있느냔 말이다!!

로직을 이해하기 위한 나으 노력 ㅎ

※ 풀이
생각의 전환이 필요한 문제이다. 내가 바라볼 수 있는 옥상 정원의 개수가 아니라 나를 바라보는 옥상의 개수를 구하는 것이다.

1. stack이 아니라 단순 스택이라고 불리는 내림차순, 올림차순을 유지하는 stack을 만드는 것이다.
2. 10, 3, 7, 4, 12, 2라고 했을 때 10은 일단 stack에 넣는다. [10] 10은 맨 왼쪽에 있기 때문에 바라볼 수 있는 옥상이 없다.
3. [10,3]은 3을 바라볼 수 있는 옥상 10이 있기에 len(stack) - 1(자기 자신을 바라볼 수 없으니)을 더해준다.
4. [10,7] 3을 pop하고 7이 들어간다. 이 과정을 끝까지 반복해주면 된다.

다른 분의 글을 참고하여 풀었다..

출처 >>

https://cochin-man.tistory.com/28

백준_6198_옥상 정원 꾸미기(python)

감사해요 도현씨.. ㅎㅎ

 

제출 결과