[파이썬] 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)을 공백으로 구분해 출력한다.

예제 입력 1

4

3 5 2 7

예제 출력 1

5 7 7 -1

예제 입력 2

4

9 5 4 8

예제 출력 2

-1 8 8 -1

 

 

✌ 나의 풀이

# 실패
import sys
input=sys.stdin.readline

N=int(input())     # 수열 A의 크기
A=list(map(int, input().split()))
answer=[0]*N
answer[-1]=-1
left_max=A[-1]

for n in range(N-2, -1, -1) :
    if A[n] < A[n+1] :
        answer[n]=A[n+1]
    elif A[n] < left_max :
        answer[n]=left_max
    else :
        answer[n]=-1
        left_max=A[n]

print(*answer)

문제의 테케는 통과

거꾸로(<-) answer에 값을 채움

오른쪽 값이 더 크면 오큰수

left_max가 아니라 right_max라고 했어야 했는데 😅

어쨋든 left_max가 더 크면 오큰수

현재 A[n]이 더 크면 left_max를 갱신

뭔가가 빠졌을텐데 .. 뭘 추가해야할까

 

 

🐝 다른 사람 풀이

# https://suri78.tistory.com/49
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=" ")

스택을 이용한 풀이

stack에 인덱스를 넣는다.

stack에서 가장 top에 있는 인덱스 값과 비교해서 더 큰 값이 나타나면 result에 넣는다.

오큰수를 찾으면 stack에서 pop

 

 

# https://claude-u.tistory.com/157
numbers=int(input())
num_list=list(map(int, input().split()))
stack=[]
result=[-1 for _ in range(numbers)]

for i in range(len(num_list)) :
    try :
        while num_list[stack[-1]] < num_list[i] :
            result[stack.pop()]=num_list[i]
    except :
        pass
    stack.append(i)

for i in range(numbers) :
    print(result[i], end=' ')

 

위랑 알고리즘이 같다.

stack이 비어있으면 except문이 실행되어 아무것도 하지 않는다.

 

 

# https://inspirit941.tistory.com/78
_=input()   # len(arr) 값과 같아서 패스
arr=list(map(int, input().split()))
stack=[]

# 값이 없으면 -1을 입력해야 하므로, 기본값 -1 설정
result=[-1 for _ in range(len(arr))]

# arr 맨 앞부터 시작, i는 각 배열의 index
for i in range(len(arr)) :
    # 스택 맨 위의 값(arr[stack[-1]])보다 arr[i]의 값이 더 클 결우=오큰수의 정의
    while len(stack) != 0 and arr[stack[-1]] < arr[i] :
        # 스택의 값을 빼고, result에 arr[i] 값을 입력
        result[stack.pop()]=arr[i]
    # while문을 빠져나왔으면, 현재 arr[i] 값을 stack에 저장
    stack.append(i)

print(*result)

 

for문 안 쓰고 print(*result)로 요소들 출력하는거 기억해둬야지.

 

 

 

문제 출처 💁‍♀️ 백준