[백준알고리즘] 17298번: 오큰수 -Python

[백준알고리즘] 17298번: 오큰수 -Java

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

17298번: 오큰수

 

오큰수는 오른쪽에서 각 리스트의 요소마다 가장 먼저 나타나는 자신보다 큰 수를 출력하도록 하는 문제이다.

 

이 값을 구하기 위해서 이중 for문을 돌리면 범위가 넓기때문에 시간초과가 발생한다.

그렇기 때문에 stack을 이용해서 풀어줘야 된다.

 

 

그럼 stack에 push하고 pop하는 기준을 알아보자.

먼저 pop을 보면, stack에 element가 존재해야하고 가장 위에있는 element가 비교대상보다 작으면 pop해주면 된다.

push는 pop할 것들을 모두 pop해준 후에 비교대상이었던 값을 push해주면 된다.

 

 

여기서 처음에는 결과를 나타내는 리스트를 하나 더 만든 후에 stack안에 '값'을 넣도록 했다.

즉 3 5 2 7 이라면, 처음에 3을 넣고 5를 넣을 차례에서 3을 빼고 5를 넣고, 3에 해당하는 index에 5를 저장하는 방식으로 했다.

 

그런데 여기서 .index()를 사용하니 시간초과가 발생하는 것 같았다. 아무래도 index()는 리스트의 처음부터 끝까지 훑으면서 찾는 것 같다. 게다가 input에 중복 불가능인 조건이 없기 때문에 3 5 3 3 7 인 경우에는 5 7 7 7 -1로 출력을 해야하는데 3의 index를 찾으라고 하면 0만 나올 것이기 때문에 틀린 조건이 될 것이다.

 

 

그래서 stack안에는 해당 값의 index가 들어가야한다. 처음 입력했을 때 몇번째 index에 위치한 값인지를 넣어야 한다는 말이다. 다시 주어진 예제를 본다면 3 5 2 7에서 처음에 3의 index인 0을 push하고 5에 해당하는 index 1을 넣어줄 때에는 결과 리스트의 index 0에 해당하는 값을 5로 바꿔주고 stack에서는 pop시킨 후에 5에 해당하는 index 1을 push해주면 된다.

 

 

추가적으로 게시판에 아래와 같은 내용이 있었는데, 실험해보니 딱히 상관없었다. 패치가 된 듯하다.

 

코드는 아래와 같다.

 

import sys

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

input = list(map(int, sys.stdin.readline().split()))
stack = []
result = [-1 for _ in range(N)]

stack.append(0)
i = 1
while stack and i < N:
    while stack and input[stack[-1]] < input[i]:
        result[stack[-1]] = input[i]
        stack.pop()
    
    stack.append(i)
    i += 1

for i in range(N):
    print(result[i], end = " ")

# print(result[-1])

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다