옥상 정원 꾸미기 백준 6198번 스택

https://www.acmicpc.net/problem/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이다.

---

뭔가 직관적으로 느낌 자체는 지난번 풀었던 탑과 비슷한 기분이 듭니다. 다만 탑의 경우에는 자신보다 높은 것을 찾는 것이었지만 이번에는 자신보다 높은 것이 나오기 전까지의 수를 구하게 됩니다. 마찬가지로 해당 문제는 스택으로 구분을 합니다.

다만 지난번 문제는 시간 제한 1.5초에 최대 길이 500,000이었다면 이번 문제는 1초에 80,000이기 때문에 어쩌면…? 하는 생각으로 완전탐색을 먼저 시도해보았습니다.

num = int(input())
garden_list = []
for i in range(num):
    garden_list.append(int(input()))
    
sum_list = []
for x in range(num-1):
    for y in range(x+1,num):
        if garden_list[x] < garden_list[y]:
            sum_list.append(y-x-1)
            break
sum_list.append(0)
print(sum(sum_list))

코드는 간단해보였지만 역시 시간초과 스택을 사용해서 풀어야 한다.

이번에도 마찬가지로 스택으로 하나씩 살펴보면서 O(n)으로 문제를 풀 수 있는가? 곰곰히 생각해보았다. 생각보다 쉽게 풀렸는데 이유는 바로 어느 관리인이 몇개의 정원을 볼 수 있는지는 생각하지 않아도 된다. 총 개수만 중요하다.

10 - 3- 7 - 4 - 12 - 2

일단 스택에다가 10을 넣어보고 그 다음은 3을 넣는데 이때 3은 10보다 작습니다. 볼 수 있으니 그대로 넣습니다.

[10,3]

그 다음은 7입니다. 스택의 가장 위에 올라와 있는 3과 비교했을때 7이 더 크니 3의 인덱스와 7의 인덱스 차이 그리고 여기서 1을 뺀 값을 sum을 구하는 변수에다가 넣어줍시다.

[10,7]

그리고 이어서 (무한루프) 7과 10을 비교했을때 7은 10보다 작으니 여전히 볼 수 있습니다. 넣어줍시다. 이렇게 4까지 넣습니다.

[10,7,4]

이제 12를 넣을때 하나씩 비교를 해봅시다.

4와 12를 비교할때 12가 더 큽니다. 4는 더이상 볼 수 있는게 없습니다. 인덱스 차이 - 1 만큼 더해줍니다 +0

7과 12를 비교할때 12가 더 큽니다. 마찬가지로 인덱스 차이 -1 만큼 더해줍니다 +1

10과 12를 비교할때도 마찬가지 입니다. +3

이제 스택은 비었습니다. 12를 넣습니다

[12]

마지막으로 [2]를 넣게 되었지만 for문은 끝났습니다. 이제 남은 스택을 보면

[12,2] 이렇게 들어 있습니다. 인덱스의 가장 마지막과 첫번째의 차이를 더합니다 + 1

총 5개의 정원을 서로 볼 수 있습니다.

num = int(input())
garden_list = []
for i in range(num):
    garden_list.append(int(input()))
 
stack_list = []
count=0
for i in range(num):
    if not stack_list:
        stack_list.append([garden_list[i],i])
        continue
        
    if stack_list[-1][0]>garden_list[i]:
        stack_list.append([garden_list[i],i])
    else:
        while stack_list:
            if stack_list[-1][0]<=garden_list[i]:
                count+=(i-stack_list.pop()[1]-1)
            else:
                break
        stack_list.append([garden_list[i],i])
        
if stack_list:
    count += (stack_list[-1][1] - stack_list[0][1])
    
print(count)

접근 방법 자체는 틀렸다고 생각하지 않는데… 틀렸다고 나오네요 조금만더 고민해보고 영모르겠으면 답을 봐야 겠습니다.

• num = int(input())
  stack=[]
  ans = 0
  for i in range(num):
  h = int(input())
  while (stack and stack[-1] <= h):
      stack.pop()
  ans += len(stack)
  stack.append(h)
  print(ans)
  

하루정도 더 고민을 하다가 바킹독의 정답지를 파이썬 형태로 옮겨 적었습니다.

비교도 안되게 간단하네요….. 한번 살펴봅시다.

예시는 다시 10 - 3 - 7 - 4 - 12 - 2를 봅시다.

일단 10이 들어 왔습니다. while은 아무것도 들어있지 않으니 바로 넘어갑시다. 아직 스택에는 아무것도 안들어 있으니 지나 갑시다.

[10] 0

3을 봅시다. 10보다 3은 크지 않습니다. ans는 스택의 길이는 1이 들어갑니다. 그리고 스택에 넣습니다.

[10,3] 1

이제 7을 넣어봅시다. 스택에는 3이 있고 7은 이보다 큽니다. 3을 팝하게 됩니다. 그리고 다시 while을 돌아보는데 7은 10보다 크지 않습니다. 다시 스택의 길이인 1을 추가하고 7을 넣습니다.

[10,7] 2

4를 넣습니다. 4는 7보다 크지 않습니다. 스택의 길이인 2를 더하고 4를 넣습니다.

[10,7,4] 4

이제 12를 넣어 봅시다. 12는 4,7,10 스택에 들어 있는 어떤 숫자보다 큽니다. 그러면 스택에는 아무것도 들어있지 않습니다. 즉 더할 것도 없습니다.

[12] 4

마지막으로 2를 넣어줍시다. 그러면 조건에 따라서 1을 더해주고 마무리 합니다.

[12,2] 5

…. ㅋㅋㅋ 과연 코테는 올해안에 준비를 마칠 수 있을까요