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

※ 접근법

옥상의 개수가 최대 팔만 개였기 때문에 단순 이중 for 문을 돌면 시간 초과가 발생할 것이라고 생각을 했다. 높이를 정렬을 하면 안 됐기 때문에 느낌상 스택을 사용해야 할 것 같았다.

 

※ 풀이

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

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이 들어간다. 이 과정을 끝까지 반복해주면 된다.

import sys
input = sys.stdin.readline

n = int(input())

s = []
count = 0
for i in range(0,n):
    x = int(input())
    if len(s) == 0:
        s.append(x)
        continue
    else:
        while len(s) > 0 and x >= s[-1]:
            s.pop()
        count += len(s)
        s.append(x)

print(count)

  ※ 회고

풀어봤던 문제랑 비슷하다는 느낌을 받았다 => 시간 복잡도, 문제 요구사항을 고려 해봤을 때 stack을 사용해야 할 것 같았다. => 하지만 stack을 사용한다 해도 결국 이중 포문 로직이랑 별반 차이가 나지 않았다. => 이때 생각의 전환을 했어야 했다.

생각이 한 곳으로 매몰됐을 때 알고리즘이 떠오르지 않는다면 생각의 전환이 필요한 것 같다.