[백준] 17298번 오큰수 (Python)

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

17298번: 오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

 

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

n = int(input())

num_list = list(map(int, input().split()))
num_list.reverse()
big_list=[]
result_list=[]
for i in num_list:
    while big_list:
        if big_list[-1] <= i:
            big_list.pop()
        else:
            result_list.append(big_list[-1])
            break
    
    if len(big_list)==0:
        result_list.append(-1)
    big_list.append(i)

result_list.reverse()
print(" ".join(map(str, result_list)))

분류별로 문제를 풀고 있어서 스택관련 문제인걸 알고있었는데그럼에도 불구하고 처음엔 아예 풀지 못했거나 시간 초과만 띄웠다.  

 

이 문제를 푼 이후 스택에서 이와 비슷한 유형의 문제가 몇 보여서 유형을 암기하고 넘어가면 좋을것 같았다.

 

문제풀이

대다수 문제를 풀때 왼쪽부터 접근하는데 

개인적으로 가장 오른쪽 수에는 "-1"만 가능하다는 점에서 구현이 쉬울것 같다고 생각하여

리스트를 역순으로 바꾸고 시작하였다.

 

 

 while big_list:
        if big_list[-1] <= i:
            big_list.pop()
        else:
            result_list.append(big_list[-1])
            break

1. 오른쪽부터 원소를 추가한 big_list[-1]보다 현재 수가 크거나 같다면

이후의 모든 원소들도 big_list[-1]이 아닌 현재 수가 오큰수가 되므로 체크할 필요가 없게된다.

따라서 big_list를 pop해준다.

 

처음 구현시 이 부분을 놓치게 되면 출력은 동일하지만 시간 복잡도가(n^2)이므로 시간초과로 풀지 못한다.

 

2. 오른쪽부터 원소를 추가한 big_list[-1]보다 현재 수가 작다면

big_list[-1]을 결과에 추가한다

 

    if len(big_list)==0:
        result_list.append(-1)

big_list가 비었다면 두가지 경우의 수가 존재하는데

 

1. 위의 코드를 전부 실핼하고서도 우측의 모든 수보다 현재 수가 크서 모든 big_list가 pop되었거나

2. 가장 오른쪽 수인 경우이다.

 

이때 결과에 -1을 추가해준다