[백준 | 골드5] 17298: 오큰수(다시 풀기)

https://www.acmicpc.net/problem/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

 

문제풀이

문제해결

시간초과

반복문 돌면서 현재 값보다 오른쪽에 있으면서 and 현재값보다 큰 값은 스택에 넣기

스택의 맨 앞에 있는 숫자 출력

시간 초과 ㅜㅜ 역시 골드 문제는 쉽지 않은가보다

import sys

n = int(sys.stdin.readline())
num_list = list(map(int, sys.stdin.readline().rstrip().split()))

for i in range(n) :
    stack = []

    now_value = num_list[i]
    for j in range(i+1, n) :                #ai보다 오른쪽에 있는 값 순회
        if num_list[j] > now_value :        #ai보다 큰수를 스택에 넣기
            stack.append(num_list[j])
    if len(stack) > 0 :
        print(stack[0], end=" ")
    else :
        print(-1, end=" ")

 

다시풀이

보고 풀긴 풀었는데 잘 모르겠다

나중에 좀 더 성장하고 다시 풀어보자 🤣🤣🤣🤣😂😂🤣😅😅

 

[주요내용]

1. 모든 수의 오큰수를 찾아야한다.

=> 아직 오큰수를 찾지 못한 수(자신 값보다 큰 값을 찾은 수)를 담는 스택을 하나 만든다.

=> 그리고 수열을 순환하며 스택이 비어있을 경우, 자신의 인덱스를 스택에 담고 순서를 넘기도록 한다.

 

 

2. 현재 비교하는 수열의 수가 스택의 꼭대기에 해당하는 인덱스의 수보다 큰 경우

=> 스택의 원소를 모두 pop 하면서 현재 수로 바꿔준다.

 

[주요변수]

stack : 오큰수를 찾지 못한 수열 값의 인덱스를 저장하는 배열

result : 찾은 오큰수를 보관하는 배열

 

 

1. 입력 받은 숫자 리스트 탐색 num_list[0] ~ num_list[n]

2. 결과값을 저장할 result는 -1로 초기화(오큰수가 없는 경우는 -1 출력)

3. 스택이 비어있지 않은 경우 반복

  3-1. 자신 값 num_list[i]가 스택의 꼭대기의 인덱스의 값보다 큰 경우 반복

   3-1-1. 스택의 꼭대기 값은 자신 값보다 작으므로 stack.pop()

   3-1-2. result의 스택의 꼭대기의 인덱스 값 자리에 찾은 오큰수 넣기

4. 스택이 비어있는 경우

 4-1. 자신의 현재 인덱스를 스택에 넣고 다음 인덱스 탐색 

import sys

n = int(sys.stdin.readline())
num_list = list(map(int, sys.stdin.readline().rstrip().split()))
stack = []
result = [-1] * n

for i in range(n) :
    while stack :
        if num_list[i] > num_list[stack[-1]] :      #현재 비교대상 값(num_list[i])과 스택의 꼭대기에 인덱스의 값과 비교
            result[stack.pop()] = num_list[i]
        else :
            break
    stack.append(i)

print(*result)