[오늘의 문제]
https://www.acmicpc.net/problem/17298
[오늘의 학습 키워드]
- 스택, 단조 스택
1. 문제 설명

문제를 보면 중복이 없는 수열 A가 주어집니다.
현재 위치를 기준으로 다음 위치의 값과 비교할 때 다음 값중 가장 먼저 오는 가장 큰 값을 찾으려 합니다.
즉 현재 값 기준 오른쪽 값들 중 가장 왼쪽에 있는 큰 값을 찾는 것입니다.
따라서 주어진 예제를 보면
3 5 2 7 이 주어질 때
3을 기준으로 다음으로 큰 값은 5이고
5를 기준으로 다음으로 큰 값은 7
2를 기준으로 다음으로 큰 값은 7
7을 기준으로 다음으로 큰 값은 없으니 -1이 들어가는 것 입니다.
[제한사항]
- 시간 제한 1초
- 메모리 제한 512MB
- 1 ≤ N ≤ 1,000,000
- 1 ≤ Ai ≤ 1,000,000
- 중복은 없음
2. 접근 방식
문제만 보면 단순히 완전탐색을 실시해서 해결하는 문제 같지만 1초에 최대 100만번 탐색을 실시하는 파이썬에서 완전 탐색은 O(N^2)번 탐색을 수행하니 무조건 시간초과가 발생합니다.
따라서 한번의 탐색 중 시간 복잡도가 O(1)에 해당하는 pop, append를 활용해 문제를 해결해 주어야 합니다.
이를 위한 코드가 단조 스택이 있습니다.
단조 스택이란 스택의 정렬된 상태를 보장하는 스택입니다.
우선순위 큐와 비슷한 느낌인데
원소가 오름차순 혹은 내림차순으로 정렬된 배열을 의미합니다.
이 배열을 이용하면 정렬되어 있지 않은 배열을 단조 스택으로 만드는 과정에서 발생하는 정보들을 유용하게 사용할 수 있습니다.
대표적인 스택을 이용한 완전 탐색기법중 하나로 브루트포스 알고리즘은 O(N^2)이 발생하는데 이 알고리즘은 O(N)번으로 수행이 가능합니다.
3. 코드
import sys
input = sys.stdin.readline
N = int(input())
numbers = list(map(int, input().split()))
# 정답을 저장할 배열과 임시로 저장할 stack
answer = [-1] * N
stack = [] # stack에는 index를 저장
# N번 반복 수행
for i in range(N):
while stack and numbers[i] > numbers[stack[-1]]: # 스택에 값이 존재하는데 해당 값의 마지막 값이 현재 비교하려는 값보다 작은경우
answer[stack[-1]] = numbers[i] # 해당 값은 주어진 조건을 만족하는 값 이므로 answer 업데이트
stack.pop() # 임무를 완료한 stack의 index 는 pop으로 제거
stack.append(i) # stack이 없다면 stack에 index 넣어주기
print(*answer)
[코드 설명]
코드 자체는 단순합니다.
입력받은 numbers를 index를 이용해 접근하고 탐색을 실시하며 stack에 append 하고 pop 과정을 수행할 겁니다.
우선 비교하기 위해서 정답을 초기화 해줍니다.
비교대상이 없는 경우 -1을 출력해야 하니 answer를 N개 만큼 -1로 생성해 주었습니다.
1. N번 반복을 수행하는데, 첫 번째 index 0은 stack에 바로 넣어주어야 합니다.
2. stack이 존재한다면 현재 index와 stack에 저장한 index를 비교해줍니다.
3. 현재 stack의 -1 은 index 0을 의미하는데 이는 가장 왼쪽 값입니다.
4. 가장 왼쪽값과 그 다음번 index값을 비교하는데 다음번 index값인 numbers[i] 가 더 크다면 이는 조건을 만족하므로
stack[-1] 번 index 위치에 해당 값이 들어와야 합니다.
5. 따라서 초기화 한 answer의 index에 맞춰 값을 넣어줍니다.
예제를 통해 더욱 정확한 동작을 살펴 보겠습니다.

여기서 index를 의미하는 i는 1인데 0번째 값은 stack에 값이 없기 때문에 stack에 0이 들어간 상태이고, 1과 비교해 줍니다.
numbers[0] 과 numbers[1]을 비교하는데 1이 더 크니 answer[0] 번째 위치에 numbers[1]의 값이 와야 합니다.
그러면 0번 index는 임무를 완수했으니 stack에서 제거해 줍니다.
이제 다시 stack에 index 1을 넣어줍니다.

그 다음 탐색을 하는데 numbers[1] 은 5이고 numbers[2]는 2 입니다.
따라서 while문 조건을 만족하지 않으니 stack에 2를 넣어줍니다.

다음 index는 3 인데 해당 값은 7입니다. 7과 가장 마지막에 들어간 index는 2입니다.
이 둘을 비교하면 당연히 index 2 보다 index 3 이 더 크니 index 2번 위치에 7이 들어갑니다.

동일하게 2는 탐색이 완료되었으니 stack에서 제거해주고 stack에 1이 남은 상황입니다.
여전히 비교 대상은 index 3의 7값을 비교하는데 index 1은 5로 더 작은 index 1번 위치에도 7이 들어가게 됩니다.

값이 들어간 이후 마지막 반복문을 수행하는데 stack에 값을 넣으면 반복문이 그대로 종료됩니다.
당연히 마지막 값을 기준으로 모든 값을 탐색하였으니 반복문이 종료되고 answer의 마지막 값은 초기화 되지 못하고 종료되는 것입니다.
이를 에스터리스크로 풀어서 출력해 주었습니다.
4. 결과

[회고]
이번 문제를 해결하며 단조 스택을 처음 알았습니다.
처음 작성한 코드의 경우 입력받은 배열을 슬라이싱 하여 2개의 스택으로 나누고, 나눈 스택의 왼쪽의 마지막 값과 오른쪽의 첫 번째 값을 기준으로 비교 후 조건이 성립하면 answer에 업데이트 하고 모든 비교가 끝나도 업데이트가 안되면 -1을 업데이트 하도록 하였습니다.
그러나 이 코드의 경우 파이썬의 배열 슬라이싱이 애초에 O(N^2)에 해당하고, 완전 탐색을 이용해 코드를 비교하니 시간이 오래걸릴 수 밖에 없었습니다.
그래서 수정한 코드가 O(1) 시간 복잡도를 가지는 pop, append 를 활용하는 방식 이었는데 단순히 코드 자체만 보면 O(1)이 맞으나 reverse, 새로운 배열에 append, pop 동작이 수행되어 결국에는 이 코드도 O(N^2)이 되었습니다.
그 다음은 queue를 활용해 appendleft() 와 popleft()를 시도하였는데, 이 역시 탐색 과정에서 완전 탐색이 발생하니 어쩔 수없이 O(N^2)번 탐색을 실시하게 되었습니다.
도저히 답이 보이지 않아 질문 게시판을 보던 중 단조 스택을 알게 되었습니다.
스택의 순서를 보장하는 스택까지는 이해했는데 코드를 보고 어떻게 동작하는지 이해가 되지 않았습니다.
코드의 구조를 1시간 동안 계속 뜯어보며 동작 과정을 유심히 살펴보았고 결국 순서대로 탐색하여 O(N)번에 탐색하는 것을 알게 되었습니다.
다음 비교값이 없거나, 현재값보다 작은 경우 새로운 배열 stack에 넣어주고 만약 큰 경우는 정답을 초기화 하여 스택이 비거나 조건이 맞지 않을 때까지 탐색을 계속 실시하는 것 이었습니다.
즉 이러면 배열에서 큰 값을 찾아서 그 값을 기준으로 이전에 탐색한 값들을 순서대로 비교하니 배열의 순서가 보장되는 것 이었습니다.
단조 스택이란 개념을 처음 알았고, 아직 자료 구조 알고리즘 지식이 부족하다 생각하는 계기가 되었습니다.
이번 기회를 계기로 더욱 열심히 알고리즘 문제를 해결하며 CS 지식을 늘려 가겠습니다.
'알고리즘' 카테고리의 다른 글
[백준] 1987 알파벳 - 골드 4 (0) | 2025.04.10 |
---|---|
[백준] 2206 - 벽 부수고 이동하기 - 골드 3 (0) | 2025.04.09 |
[백준] 1759 암호 만들기 - 골드 5 (0) | 2025.04.07 |
[백준] 20304 - 비밀번호 제작 - 플레 5 (0) | 2025.04.01 |
[백준] 16987 - 계란으로 계란치기 - 골드 5 (0) | 2025.03.31 |