BOJ 17298번 오큰수 (Stack) 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(N)을 공백으로 구분해 출력한다.

 

NGE 오큰수?

 오 큰 수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.

3 2 4 8 9

NGE(n) n은 index입니다

n 이 1이라고 치면 3보다 크면서 오른쪽에 있는 수는

8,9가 되겠네요 여기서 가장 왼쪽에 있는 수는 8입니다.

 

내가 접근한 방법

그냥 스택안쓰고 어거지로 2중 for문써서

arr[index(n)]보다 큰 수가 나오면 바로 break 했는데

A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다

백만 개의 숫자가 입력되기 때문에 당연히 시간 초과가 납니다. (0(n^2))

당연한 건데 저는 4번이나 똑같은 방법으로 시간 초과를 받았습니다.

이 문제는 스택을 활용해서 2중 for문을 사용하지 않고해결할 수 있습니다.

처음엔 도대체 for문을 쓰지않고 나보고 도대체 어쩌라는건가 싶었는데

풀고나서 티어보니까 골드4문제더라구요 원래 어려운문제같습니다.

 

풀이(python)

 

n = int(input())
arr = list(map(int, input().split()))

Oken = [-1] * n
stack = [0]



for i in range(1,n):
    if arr[i] > arr[stack[-1]] and stack:
        while(stack):
            if arr[stack[-1]] < arr[i] : 
                Oken[stack.pop()] = arr[i]
            else: 
                break
        stack.append(i)
    else:
        stack.append(i)
print(*Oken)

5

3 2 4 8 9

이게 입력으로 들어왔다 하겠습니다.

arr = [3 2 4 8 9]

오 큰 수를 담는  Oken배열을 만들어줍니다.

Oken = [-1] * n

그리고 스택을 하나 만들어줍니다

stack = [0] 스택에는 index를 넣어줄 겁니다

for문을 돌리는데 1부터 시작합니다.

arr [stack [-1]] < arr [i]

arr [stack [-1]]은 3이고

arr [i]는 2죠

작으니까 stack에 i를 넣어줍니다(1)

stack = [0,1]

이제 i는 2이고

arr [stack [-1]] < arr [i] 이걸 다시 하면

2 < 4

이렇게 큰 수를 만났을 때는 스택이 빌 때까지 //stack = [0,1]

arr [stack [-1] ] < arr [i]이라면

Oken [stack.pop()]에 4(오 큰 수)를 넣어줍니다. //pop은 최상단의 원소를 리턴하고 삭제합니다

이 과정을 마치면

Oken  = [4,4,-1~]

이 되어있겠죠

 

이 문제는 자료구조의 중요성을 느끼게 해 주는 엄청 좋은 문제 같습니다