6198

날짜 : 2023. 10. 08

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/6198

 

 

코드

import sys

n = int(sys.stdin.readline())
num = list()

for _ in range(n):
    num.append(int(sys.stdin.readline()))  # 입력받음
num.append(int(1e10))  # 마지막 공원 체크

res = [0] * (n + 1)
stack = list()
stack.append([0, num[0]])

for i in range(1, n + 1):
    # print(stack)
    if len(stack) == 0:  # 스택이 빈 경우
        stack.append([i, num[i]])
        continue
    flag = False
    while stack:
        idx, value = stack[-1]  # 빌딩 위치, 높이
        if num[i] < value:  # 현재 빌딩이 이전 빌딩보다 낮은 경우
            stack.append([i, num[i]])  # 삽입
            break
        res[idx] = (i - idx - 1)
        stack.pop()
        flag = True
    if flag: stack.append([i, num[i]])

t = 0
# print(res)
for i in res: t += i
print(t)

 

 

풀이

- n의 최대 개수가 80000이기 때문에 이중 for문을 사용해서 넣는 경우에 시간초과가 발생한다.

- 그러므로 스택을 사용해 해당 빌딩의 높이에 따라 앞선 빌딩을 pop 하는 방식으로 문제를 풀이한다.

- 먼저 조건에 따라 입력받은 후, 각 빌딩 위치에 따라 볼 수 있는 빌딩의 개수를 저장할 리스트를 초기화한다.

- 그 다음 스택을 만들고 맨 처음 위치의 빌딩의 인덱스와 높이를 삽입, 그 다음 for문을 실행한다.

- 먼저 스택이 빈 경우는 넣어주어야 하기 때문에 삽입 후 곧바로 continue

- 아니라면 스택 가장 위의 원소에서 인덱스와 높이를 추출, 해당 높이보다 현재 높이가 작다면(앞 빌딩에서 보이는 경우), 스택에 push 후 다음 인덱스로 이동

- 만약 해당 케이스가 아니라면(앞전 빌딩에서 현재 위치의 빌딩을 볼 수 없는 경우), 뽑아낸 인덱스 위치에서 볼 수 있는 빌딩의 개수는 (현재 위치 - 인덱스 위치 - 1)이 되며, 해당 값을 res 리스트의 인덱스 위치에 저장한다.

- 그 다음 해당 스택 가장 위의 원소를 pop 하고, 현재 위치의 인덱스와 높이값을 넣어줘야 하기 때문에 플래그를 True로 설정한 후 while문을 계속 돌린다.

- while문을 탈출한 후에는 현재 위치의 인덱스와 높이값을 넣는다.

 

 

알게된 점

- 이중 for문으로 푼다면 간단히 풀 수 있는 문제겠지만 시간초과라는 요소가 있어 자료구조, 그 중 스택으로 풀어야 하는 문제였다.

- 디버깅 과정에서 원소를 넣고 빼는 과정에서 마지막 부분이 확실하게 구현되지 않아 로직을 고민했고, 마지막에 지정된 높이보다 무조건 큰 빌딩을 넣어 끝자락 빌딩의 값들을 설정할 수 있도록 구현하였다.

- 한시간 정도 고민해서 풀었지만 자력으로 풀었다는 것에 의의를 두고 싶다.

 

 

참고 사이트

-