[알고리즘] 백준 2493번 Python

 

분류

스택

 

혼자 힘으로 해결 했는가?

X

 

느낀 점

스택 문제를 많이 풀지 않았기 때문에 억지로 스택을 활용하려고 하다가 시간 초과를 맞이했고 결국 실패했다.

스택 하나만으로 이 문제를 어떻게 해결해야하는지 감이 오지 않아 구글링을 해 보았고

Monotone 스택 유형임을 알게 되었다.

 

그와 동시에 이 문제에서 제시하는 사고 흐름은 반드시 익혀야겠다는 생각을 했다.

---

 

내가 작성한 코드 

오답

import sys

from collections import deque

N = int(input())

tower = list(map(int, sys.stdin.readline().rstrip().split()))


stack = deque()

for i in range(N):
    tower[i] = (tower[i], i + 1)


tmp = deque()

ans = []

for i in tower:
    if not stack:
        ans.append(0)
        stack.append(i)
    else:
        found = False
        if stack[-1][0] < i[0]:
            while stack:
                if stack[-1][0] >= i[0]:
                    found = True
                    ans.append(stack[-1][1])
                    break
                tmp.append(stack.pop())

            while tmp:
                stack.append(tmp.pop())
        else:
            found = True
            ans.append(stack[-1][1])
        if not found:
            ans.append(0)
        stack.append(i)


for i in ans:
    print(i, end=" ")

 

 

---

정답을 받은 코드

import sys

from collections import deque

N = int(input())

tower = list(map(int, sys.stdin.readline().rstrip().split()))


stack = deque()


ans = []


for i in range(N):

    # i번째 탑에 대해서 스택 내부에 나보다 크거나 같은 대상을 만날 때 까지
    # 스택을 비운다.
    # 단, 출력 값이 탑 중에서 몇 번째인지를 출력 해야하기 때문에
    # 스택에 탑의 높이와 해당 탑이 몇 번째인지 저장한다.

    found = False

    if not stack:
        stack.append((tower[i], i + 1))
        ans.append(0)
    else:
        while stack and not found:

            if stack[-1][0] < tower[i]:
                stack.pop()
            else:
                found = True
                ans.append(stack[-1][1])
                stack.append((tower[i], i + 1))

        if not found:
            stack.append((tower[i], i + 1))
            ans.append(0)

for i in ans:
    print(i, end=" ")

 

---

틀린 이유에 대한 고민

 

처음 접근 시 검사를 해야하는 탑의 높이에 대해 스택 내부에서 더 낮은 탑을 모두 뺀다는 발상은 했다.

 

그러나 나는 현재 탑보다 더 작은  탑의 정보를 다시 스택에 담아야 한다고 생각을 했다.

 

다시 생각해보면 앞선 더 작은 탑은 문제의 조건에 따라 이제는 딱히 필요가 없다.

 

문제의 요구사항을 만족하기 위해서는 정보들이 담긴 일련의 데이터, 즉 배열에서

 

단조 증가 혹은 단조 감소만 하면 된다.

 

왜냐하면 앞선 인덱스의 값이 더 크면 그 앞은 더 이상 의미가 없게 되기 때문이다.

 

하나의 스택만 사용하지 않고 다시 스택을 되돌리는 연산이 추가가 되었기 때문에

 

각 원소마다 N번, 그리고 최악의 경우 N번째에서 앞선 N개를 모두 되돌려야 하기 때문에

 

시간복잡도가 O(N^2)가 되었고

 

입력값이 50만이기 때문에 시간초과가 발생했다.

 

그러나 되돌릴 필요 없이 현재까지의 스택 중 가장 큰 값을 찾으면 다음으로 넘어가면 된다.

---

비슷한 문제들

 

백준 6198번

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

6198번: 옥상 정원 꾸미기

 

백준 17298번

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

17298번: 오큰수