[백준/BOJ] gold4 - 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(2),..., NGE(N)을 공백으로 구분해 출력한다.

728x90

▶풀이

이번 문제는 Stack을 이용해서 푸는 문제이다.

단순한 구현으로 풀면 바로 시간 초과가 난다. (아래 단순 구현 코드 참고)

 

Stack으로 푸는 방법은 생각보다 복잡하지 않다

Stack이 비어있지 않고, Stack 마지막에 있는 값에 해당하는 숫자와 새로 들어오는 숫자만 비교하면 된다.

비교했을 때 오른쪽(새로 들어오는 값)이 크다면 answer에 채워주고 다음 Stack을 pop 하면 된다.

 

그럼 자연스럽게 자기 값보다 큰 값으로 채워지게 된다.

말로 설명하기는 조금 힘든 문제이다. (내가 말을 못 해서 그럴 수도 있다.)

아래 코드를 문제랑 함께 보면 쉽게 이해할 수 있다.

n = int(input())
arr = list(map(int, input().split()))
answer = [-1 for _ in range(n)]
stack = []

for i in range(n):
    while len(stack) != 0 and arr[stack[-1]] < arr[i]:
        answer[stack.pop()] = arr[i]
    
    stack.append(i)

for ans in answer:
    print(ans, end=' ')

 

아래는 시간초과난 코드이다.

단순한 구현으로 풀면 시간초과가 날 수 있기에, 그렇게 풀었다면 다른 코드로 새로 풀어야 한다.

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

for i in range(n):
    if i == n - 1:
        answer.append(-1)
        continue
    
    a = arr[i]
    check = 0
    for j in range(i + 1, n):
        b = arr[j]

        if a < b:
            answer.append(b)
            check = 1
            break
    if check == 0:
        answer.append(-1)

for ans in answer:
    print(ans, end=' ')