문제

' 17298번 오큰수 '
https://www.acmicpc.net/problem/17298

Check point

📌 스택 (stack)

💡 스택이란?

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
  => 데이터의 삽익과 삭제가 데이터의 가장 한쪽 끝에서만 일어나는 자료구조

💡 스택 특성

• 선형 구조 : 자료 간의 관계가 1 : 1 ( vs 트리 (비선형 구조 = 1 : N 관계))
• 후입선출 (Last-In-Frist-Out) : 가장 마지막으로 추가된 항목을 가장 첫번째로 제거

💡 스택 연산

• push : 데이터 삽입
• pop : 데이터 삭제 -> pop() : 가장 마지막 데이터 삭제
• top : 가장 마지막에 삽입한 데이터를 삭제하지 않고 return
• isEmpty : 스택이 비어있는지 여부 확인
• peek : 스택의 top에 있는 원소를 반환

📌 풀이 조건

• 이중 for문을 쓴다면 아주 손쉽게 풀리지만 시간초과가 일어나므로 stack을 써야한다.
• 결과값을 저장할 리스트를 생성한다. 이때, 큰 수 가 없을 경우 -1을 출력해야 하므로 N개의 -1이 저장된 리스트로 생성한다.
• 입력 리스트를 순회하면서 stack 에 인덱스와 해당 값을 추가한 뒤, 해당 값 보다 큰 값을 만난다면 해당 인덱스와 같은 결과값을 변환해 준다.
  
  

코드

python

N = int(input())
lst = list(map(int, input().split()))
stack = []
result = [-1 for _ in range(N)]  # 결과값을 출력할 리스트 / 기본값은 -1 이고 큰 수가 나오면 바꾸는 형식 
for i in range(N):
    # stack에 들어 있는 값 중 lst[i]보다 작은 값의 인덱스를 모두 찾고, 해당 인덱스의 결과값을 lst[i]로 변환 
    while stack and stack[-1][1] < lst[i]:  # 스택이 빈 리스트가 아니고 스택 마지막 값보다 클 때
        result[stack[-1][0]] = lst[i]  # 해당 인덱스의 결과값 변환
        stack.pop()  # 스택에서 제거
    stack.append([i, lst[i]])  # 스택에 추가
print(*result)

정리 코드

N = int(input())
lst = list(map(int, input().split()))
stack = []
result = [-1 for _ in range(N)]
for i in range(N):
    while stack and stack[-1][1] < lst[i]:
        result[stack[-1][0]] = lst[i]
        stack.pop()
    stack.append([i, lst[i]])
print(*result)