백준 - 2493번(스택)

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

2493번: 탑

 

import sys

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

arr = list(map(int,sys.stdin.readline().split()))
ans = [0 for _ in range(n)]

tmp = [[arr.pop(),len(arr)+1]] #가장 오른쪽에 있는 값, 해당 값이 몇번째 탑인지

while len(arr) > 0:
    t = arr.pop()
    if t >= tmp[0][0]:
        #해당 시점에 tmp안에 원소들은 전부 t에서 수신 받는다.
        while tmp:
            x = tmp.pop()
            ans[x[1] - 1] = len(arr) + 1
        tmp.append([t, len(arr) + 1])

    elif t >= tmp[-1][0]:
        while tmp:
            x = tmp.pop()
            if t >= x[0]:
                #t보다 작거나 같은 원소는 t에서 수신 받는다.
                ans[x[1] - 1] = len(arr) + 1
            else:
                #t보다 큰 원소가 존재하면 tmp에 다시 t를 넣어주고 종료
                tmp.append(x)
                break
        tmp.append([t, len(arr) + 1])
    else:
        tmp.append([t, len(arr) + 1])

print(*ans)

코드가 길진 않지만 아이디어가 생각보다 복잡했다.

탑의 끝쪽부터 탐색해야 하는 문제라서 reverse() 함수 같은걸 사용할 생각 하면 절대 안 된다.

탑의 수가 굉장히 많고 탑들의 높이로 주어지는 범위도 굉장히 크기 때문에 시간 초과가 날것이다.

arr.pop()을 해주면 O(1)의 시간 복잡도로 가장 마지막에 있는 원소부터 꺼낼 수 있다.

기본적인 원리는 다음과 같다.

만약에 이번에 꺼낸 탑의 높이가 처음으로 꺼낸 탑의 높이(즉, tmp[0][0]) 보다 크거나 같으면 tmp에 들어 있는 애들을 전부 인덱스에 맞게 넣어준다. 이유는 tmp에 들어있는 애들은 tmp[0][0] 보다 작은 애들만 들어 있기 때문이다.

그러나 만약에 t가 tmp[0][0] 보다는 작은데 최근에 넣은 tmp값 보다 큰 경우가 생길 거다. 예를 들어 6 5 7 이런 경우 말이다.

그럴 땐 t보다 작거나 같은 원소는 ans에 인덱스를 대입해 주면서 조건에 맞는 원소들을 제거해준다.

그렇지 않은 원소를 만나면 반복문을 탈출하고 tmp에 t를 대입해준다.

ans에 인덱스를 조금 편하게 대입하기 위해서 2차원 리스트를 이용해서 x [i][1]을 호출해주면 된다.

tmp가 증가할 때마다 arr은 줄어드는 부분을 생각해 보면 된다.

최종적으로 ans를 출력해주면 답이 나온다.