[백준] 17298번(python 파이썬) - 오큰수

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

17298번: 오큰수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	57663	19453	13950	32.700%

문제

크기가 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)을 공백으로 구분해 출력한다.

 

 

 

 

 

 

풀이

---

이 문제는 자료구조를 활용하는 문제이다.

시간복잡도와 상관없이 이 문제의 코드를 구현한다면 for문을 두번써서 O(n**2) 의 시간복잡도로 시간초과가 날것이다.

n이 100만이기때문에 n**2 = 100억이다. (ㅋㅋ 어림없는 숫자)

 

 

자! 자료구조를 이용해서 시간복잡도를 줄여보자!

 

O(n√n)의 시간복잡도도 불가능하다. 파이썬은 1초에 대략 2000만번의 계산이 가능한데 100만 x 1000이 되므로

10억이 나온다. (역시 어림없는 숫자 ㅋㅋ)

 

 

 

그렇다면 for문을 한번만 써서 답을 구할 생각을 해봐야 한다.

 

잠깐 생각해보자...

 

 

 

 

 

 

 

 

 

 

 

 

 

포스팅 끝...

 

죄송합니다..

 

 

 

 

나는 스택을 사용해서 이 문제를 시간복잡도 O(n) 과정으로 구현했다.

 

과정은 다음과 같다. ( deque를 이용한 stack구현 ) 

 

que = deque()

1. 초키 설정과정 -> 처음의 숫자입력을 받은 list를 arr이라고 하자

                            -> res는 -1이 n개 들어있는 리스트이다. ( 나중에 정답이 될 list)

                            -> que에는 오큰수가 정해지지 않은 숫자들의 인덱스와 값이 들어간다. (물론 arr의 값)

2. que에 첫번째 숫자의 인덱스와 해당 숫자를 넣는다. (비교할 숫자가 필요하기 때문) ex) tuple(index, value)

3. for문을 1~ n까지 돌린다. (for문에서 돌아가는 변수를 idx라고 하자)

4. for문을 돌리는 과정에서 큐가 있고 arr[idx]가  큐의 마지막 인자보다 크다면

    실행되는 while문을 적는다. (시간복잡도는 마지막에 설명 )

    -> arr[idx]가  큐의 마지막 인자보다 크다. 의 조건은 큐의 마지막 인자의 오큰수는 arr[idx]라는 말이 된다.

    -> que의 마지막 인자를 삭제( tmp = que.pop()) 그리고 res[tmp[0]] = arr[idx] 식을 적어준다.

    -> res의 해당 인덱스가 -1에서 해당 인덱스이 오큰수로 바뀜

    -> 다시 큐가 있고 다음 마지막인자(이전 마지막인자가 삭제됨)의 오큰수가 있는지 비교

    -> 반복

5. arr[idx]를 큐에 추가 (비교만 했지 오큰수를 찾지 못함)

6. 이전 과정 반복(for~ while)

 

자 시간복잡도를 설명하겠다.

 

얼뜻 보면 for 과 while을 썼기 때문에 O(n**2)처럼 보인다.

하지만 while문에서 삭제된 인자는 다시 비교되지 않는다. (오큰수가 나왔기 때문에 비교할 필요가 없어짐 )

따라서 시간 복잡도는 O(n)이 됨

 

 

구현 코드

---

from collections import deque
input = stdin.readline
n = int(input())
que = deque()
res = [-1] * n
arr = list(map(int, input().split()))

que.append((0, arr[0]))
for idx in range(1, n):
    while que and que[-1][1] < arr[idx]: # 큐의 마지막 원소가 idx보다 작다면 오큰수 조건 성립
        tmp = que.pop()
        res[tmp[0]] = arr[idx] # 큐의 마지막 원소의 인덱스를 res의 인덱스로 넣은 수 오큰수를 넣어준다.

    que.append((idx, arr[idx])) # 어짜피 마지막 과정은 인덱스로 비교한 숫자를 큐에 넣어주는 과정

print(*res) # 정답 출력