악곱 == 악성곱슬

스택

---

이 문제는 오른쪽에 있는 수들 중에서, 현재 위치보다 큰 수인데, 가장 왼쪽에 위치한 수를 찾아서 출력해야 했다. 따라서 이중 반복문을 돌며 O(N^2)으로 해결할 수 있는 문제이다. 하지만 입력이 100만이었고 시간초과가 발생한다.

따라서 1, 2번의 순회로 끝내려는 방향으로 생각해봤다. 그렇게 하기 위해서는 현재 저장된 위치와 뒤를 비교하며 바로 답을 구해나가야 한다. 그래서 만약 뒤에 숫자가 작다면 스택에 넣어서 보관하며 들고다니면 되겠다는 생각을 했다. 그리고 더 큰 수가 나오면 stack을 pop하며 출력을 하면 된다.

여기서 나는 원하는 위치에 인덱스를 바로 집어넣기 위해 미리 결과 리스트를 -1로 초기화 했고, stack에서 pop할때 해당 결과 리스트를 업데이트 해주는 방향으로 구현했다.

최악의 경우, 맨 마지막까지 탐색, 그리고 스택을 다시 전부 꺼내는 점, 출력하는 시간 까지 해서 3N 정도의 탐색시간이 걸리게 된다. O(N)으로 시간복잡도를 줄일 수 있었다.

코드는 아래와 같다.

구현

---

import sys

def solution(n):
    result = [-1] * n
    stack = [[li[0], 0]]

    for i in range(1, n):
        while stack:
            if stack[-1][0] < li[i]:
                result[stack[-1][1]] = li[i]
                stack.pop()
            else:
                break
        stack.append([li[i], i])

    for r in result:
        print(r, end=" ")

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    li = list(map(int, sys.stdin.readline().rstrip().split()))
    solution(N)