백준 17298번 오큰수

정보

문제 바로가기 [클릭]

난이도: Gold4

관련 개념: #자료구조 #스택

---

조건

시간 제한	메모리 제한
1 초	512 MB

---

문제

크기가 N인 수열 A = A₁, A₂, …, A_N이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. A_i의 오큰수는 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -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의 원소 A₁, A₂, …, A_N (1 ≤ Ai ≤ 1,000,000)이 주어진다.

---

출력

총 N개의 수 NGE(1), NGE(2), …, NGE(N)을 공백으로 구분해 출력한다.

---

예제 입출력 1

입력

4
3 5 2 7

출력

5 7 7 -1

---

예제 입출력 2

입력

4
9 5 4 8

출력

-1 8 8 -1

---

코드(파이썬)

import sys


n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
stack = [(0, nums[0])]

for i, num in enumerate(nums[1:], 1):
    if num > stack[-1][1]:
        while stack and stack[-1][1] < num:
            nums[stack.pop()[0]] = num
    
    stack.append((i, num))

for i, _ in stack:
    nums[i] = -1

print(*nums)

---

특이사항

• 풀이방법
  • 스택에 숫자와 그 인덱스를 저장
  • 지금 숫자가 스택의 마지막 숫자보다 작다면 스택에 추가
  • 크다면 스택에서 인덱스를 꺼내 nums를 업데이트
  • 아직 스택에 남은 숫자가 있다면 오큰수가 없는 숫자이므로 그 인덱스의 nums를 -1로 업데이트
  • nums 출력
• 내 코드(189,960KB, 1,320ms)에 비해 우수한 코드(바로가기, 152,408KB, 1,212ms)와 비교

  • N = int(input())
    array =list(map(int,input().split()))
    result = [-1]*N
    stack=[]
    
    for i in reversed(range(N)):
        while stack and stack[-1] <= array[i]:
            stack.pop()
        if not stack:
            result[i] = -1
        else:
            result[i] = stack[-1]
        stack.append(array[i])
            
    print(*result)
    
    

  • 입력 숫자 반복
    • 기존: 1부터 시작
    • 개선: n부터 시작
  • 결과 저장
    • 기존: nums 업데이트
    • 개선: r 리스트에 저장
  • 스택에 저장하는 값
    • 기존: 모든 숫자
    • 개선: 마지막 삽입 숫자보다 작은 숫자

---

참고문헌

-