[문제 풀이] 백준 2493

해결 과정

완전 탐색으로 풀면 안되는 문제 유형 중 하나. 시간초과가 난다는 것은, 다른 문제 풀이 방법을 의도했다는 것이다. 

해결법이 생각나지 않아 다른 분의 블로그를 참고해서 이해한 뒤, 코드는 스스로 작성해봤다.

 

stack을 활용하여 푼 풀이다. 

여기서 핵심은, 이전에 탐색 했던 탑 중, 의미없는 탑은 이후 탐색 대상에서 지워버려도 된다는 점이다. 

 

참고로 문제에서 몇 번째 인지는, 1부터 시작한다는 점을 유의하자.

 

나의 풀이

def solution():
    N = int(input())
    tops = list(map(int, input().split()))
    stack = [] # [1, 6], [2, 9], ... [번째, 탑 높이]
    answer = []

    for idx, top in enumerate(tops):
        isFound = False
        while stack:
            cur = stack[-1]
            if cur[1] > top:
                answer.append(str(cur[0]))
                isFound = True
                break
            else:
                stack.pop()
        stack.append([idx+1, top])
        if not isFound:
            answer.append("0")

    return " ".join(answer)

print(solution())

 

다른 풀이

이 분 블로그 글을 참고했다.