[알고리즘 문제 풀이][파이썬] 백준 17298번: 오큰수

백준 17298 문제 링크: https://www.acmicpc.net/problem/17298

📑 문제 설명

수열의 크기와, 수열이 주어졌을 때 각 수열의 각 자리에 대한 오큰수를 구하는 프로그램 작성.

오큰수는 각 자리에 있는 수에서 오른쪽에 위치한 숫자들 중, 각 자리에 있는 수보다 크면서 가장 왼쪽에 있는 수를 말한다.

예를 들어 3 5 2 7 이라는 수열이 있을 때
3의 오큰수는 5 2 7 중에서 3보다 크면서 가장 왼쪽에 위치한 5가 된다.
5의 오큰수는 7, 2의 오큰수는 7, 7은 오큰수가 없기 때문에 -1을 출력한다.

입력: 수열의 크기, 수열
출력: 오큰수

💡 문제 해결 방법

이 문제는 결국 못 풀어서 답지를 보고 해결했다.
(아직도 내 코드에서 어느 부분이 잘못됐는지 못 찾음...)

Tip! stack을 사용하여 index를 저장하자!

• 현재 숫자가 stack에 push되어 있는 index에 위치한 수보다 작다면 현재 숫자에 해당하는 index를 stack에 push한다.
• 현재 숫자가 stack에 저장된 index에 위치한 수보다 크다면 해당 index에 대한 오큰수를 찾은 것이므로 stack에서 해당 index를 pop한다. 그 후, 현재 숫자에 해당하는 index를 push한다.

예제: 9 5 4 8

초기 stack[0]
초기 수열 index = 1

1.index = 1 일 떄,
수열[stack[-1]] = 9(이전 숫자) > 수열[index] = 5(현재 숫자) 이므로 index = 1을 stack에 push
--> stack[1 0]

2. index = 2 일 떄,
   수열[stack[-1]] = 5(이전 숫자) > 수열[index] = 4(현재 숫자) 이므로 index = 2을 stack에 push
   --> stack[2 1 0]

3. index = 3 일 떄,
   수열[stack[-1]] = 4(이전 숫자) < 수열[index] = 8(현재 숫자) 이므로, stack.pop(=2) 하고 현재 숫자가 이전 숫자들보다 클 동안 과정 반복, 반복이 끝나면 현재 index를 stack에 push
   --> stack[1 0] --> 수열[9 5 8 8]
   --> stack[0] --> 수열[9 8 8 8]
   --> stack[3 0]

4. stack에 index 값이 남아 있는 경우는 오큰수가 없음을 의미하므로 해당 수열 자리에는 -1로 수정
   --> 수열[-1 8 8 -1]

💻 코드

꾸망쓰 코드

import sys

def check_neg(n,num_list, order):

    index_stack = list()
    index_stack.append(0)
    result = list()
    for i in range(1, n):
        if(num_list[i] < num_list[index_stack[-1]]):
            index_stack.append(i)
        else:
            num_list[index_stack.pop()] = num_list[i]
            if(len(index_stack)>0):
                while(len(index_stack)):
                    if (num_list[index_stack[-1]]<num_list[i]):
                        num_list[index_stack.pop()] = num_list[i]
                    else:
                        break
            index_stack.append(i)


    if(len(index_stack) > 0):
        for i in range(len(index_stack)):
            num_list[index_stack.pop()] = -1
    print(num_list)
if __name__ == '__main__':
    n = int(sys.stdin.readline())
    num_list = [ int(x) for x in (sys.stdin.readline().split())]
    order = sorted(num_list)
    check_neg(n, num_list, order)

정답 코드

import sys

def check_neg(n,num_list):

    index_stack = list()
    index_stack.append(0)

    for i in range(1, n):
        while index_stack and num_list[index_stack[-1]] < num_list[i]:
            num_list[index_stack.pop()] = num_list[i]
        index_stack.append(i)

    if(len(index_stack) > 0):
        for i in range(len(index_stack)):
            num_list[index_stack.pop()] = -1
    return(num_list)

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    num_list = [ int(x) for x in (sys.stdin.readline().split())]

    result = check_neg(n, num_list)
    for i in result:
        print(i, end=" ")

💟 추가적으로 알게 된 점

• while list 의미: list에 원소가 있으면 True 없으면 False