[백준] 스택, 오큰수 구하기

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

1. 문제 개요

1.1 Input

N (ex. 9)

크기가 N인 수열 A (ex. 10 1 2 3 11 4 5 6 12)

 

1.2 Output

A의 각 원소에 대한 오큰수 배열(*오큰수 NGE(I): 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수)

(ex.  [11,2,3,11,12,5,6,12,-1])

 

 

2. 문제 풀이

2.0 귀찮은 백준 입력 세팅: 여러 줄을 입력으로 받는다 (for문 활용 + sys.stdin.readline())

import sys

for y in range(2):
    if y == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = deque(map(int, sys.stdin.readline().split()))

 

2.1 진짜 단순하게 하나씩: O(n^2)

from collections import deque

answer = deque()
for t in range(n):
    now = inputs.popleft()
    for i in inputs:
        if i > now:
            answer.append(i)
            break
        else:
            continue
    if len(answer) < t+1:
        answer.append(-1)

print(*answer)

Tip: 리스트 내 원소만 출력하고 싶으면, print(*리스트)

 

2.2 reverse

탐색 문제 풀이 시 input과 output의 관계(경향)을 잘 살피고

• reverse 탐색 / 양방 탐색 등의 방법도 고려해야 함
• 발상의 전환! 반대 방향으로 탐색하면 더 효율적이지 않을까? => 본 문제에서는 여전히 O(n^2)

 

2.3 O(n^2) => O(n)으로 효율화 필요함! 

• for 문을 한 번만 쓰는 방법,, + 이미 오큰수 구한 원소는 고려 대상에서 제외하는 거,,
• 리스트 내 원소 i는 순차적으로 한 번씩 탐색 (유일한 for문)
• answer = [-1] * n
• stack!! => 오큰수를 찾지 못한 원소의 index를 stack에 저장해두고, 완료된 것은 지움으로써, 당장 필요한 원소만을 추리는 기능
  • stack = [0] 으로 시작 (base case에 대한 사전 처리)
  • while 현재 탐색 중인 i가 stack의 top보다 크면, i는 top의 오큰수가 됨! (이하이면 pass)
  • stack에서 top을 pop (이미 오큰수 구하였으므로 제거) & top의 Index 위치에 해당하는 answer의 value에 오큰수를 저장
  • while 문 끝나면 i가 stack에 append

for y in range(2):
    if y == 0:
        n = int(input())
    else:
        inputs = list(map(int, input().split()))

answer = [-1] * n
stack = [(0)]

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

Tip: stack 저장 대상에 index만 있을 수 있음!

Tip: 반복문에서 pass VS continue

pass	continue
실행할 코드가 없는 것으로 하위 코딩을 수행	하위 코딩을 건너뛰고(i번째 for문 종료) 다음 순번의 loop를 수행

 

Tip: while stack and 조건: 해당 조건문이 stack이 False인 상태에서 에러 발생!