이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 55 번째 글 입니다.
목차
골드4 : stack 문제이다.
풀이
아, 정말 아쉬운 문제였다. 하지만 배운 것이 있었다. Stack을 기본적으로 사용하는 이유은 어떤 복잡도 문제를 해결하기 위함이다. 이 부분은 뒤에 다시 살펴보도록 하자. 일단 이 문제를 단순하게 순회해서 푼다면 최악의 경우 $O(n^2)$가 걸리기 때문에 n=1,000,000인 상황에서 바로 시간초과가 난다. 그래서 이를 n에 가까운 속도로 풀어야 한다.
그렇다면 문제를 분석해보자. 오큰수는 현재 값에서 오른쪽에 있는 큰값들 중 가장 첫번째로 나오는 녀석이라고 정j의할 수 있다. 그렇기 때문에, 만약 현재값이 4인데, 다음 값이 10이면 그 10이 오큰수가 될 수 있겠다. 여기서 알 수 있는 점은 아, 큰놈이 나오면 그 전값은 이 큰놈이 오큰수가 될 가능성이 있구나. 정도이다. 그럼 이런 상황은 어떨끼?
4 3 9
이런 상황에서 4의 입장에서 3은 오큰수가 아니다. 하지만 3의 입장에서 9는 오큰수이다. 그렇다면 4의 오큰수는? 9이다. 여기서, 현재 값보다 미래 값이 큰 경우 과거값들 중에 미래 값을 오큰수로 가지는 녀석이 있을 수 있다는 결론을 내릴 수 있다.
1 7 9 7 8 3 1 4 10 3 10
7 9 10 8 10 4 4 10 -1 10 -1
자 그럼, 어떤 분기에서 이 가정이 틀릴 수 있을까? 일단 미래 값이 현재값과 같다면, 현재 값의 오큰수는 그 미래값이 아니다. 여기서 stack을 사용해보자. stack에는 다음에 나올 미래값에 의해 오큰수가 결정될 후보 위치를 말한다. 좀 어려우니 적어보자.
11
1 7 9 7 8 3 1 4 10 3 10
index : 0
value : 1
stack 현재 상태
0
index : 1
value : 7
stack top (position): 0
value : 1
오큰수 후보 발견, 답안 업데이트
stack before
0
answer before
0 0 0 0 0 0 0 0 0 0 0
stack after
answer after
7 0 0 0 0 0 0 0 0 0 0
stack 현재 상태
1
index : 2
value : 9
stack top (position): 1
value : 7
오큰수 후보 발견, 답안 업데이트
stack before
1
answer before
7 0 0 0 0 0 0 0 0 0 0
stack after
answer after
7 9 0 0 0 0 0 0 0 0 0
stack 현재 상태
2
index : 3
value : 7
stack top (position): 2
value : 9
stack 현재 상태
2 3
index : 4
value : 8
stack top (position): 3
value : 7
오큰수 후보 발견, 답안 업데이트
stack before
2 3
answer before
7 9 0 0 0 0 0 0 0 0 0
stack after
2
answer after
7 9 0 8 0 0 0 0 0 0 0
stack 현재 상태
2 4
index : 5
value : 3
stack top (position): 4
value : 8
stack 현재 상태
2 4 5
index : 6
value : 1
stack top (position): 5
value : 3
stack 현재 상태
2 4 5 6
index : 7
value : 4
stack top (position): 6
value : 1
오큰수 후보 발견, 답안 업데이트
stack before
2 4 5 6
answer before
7 9 0 8 0 0 0 0 0 0 0
stack after
2 4 5
answer after
7 9 0 8 0 0 4 0 0 0 0
오큰수 후보 발견, 답안 업데이트
stack before
2 4 5
answer before
7 9 0 8 0 0 4 0 0 0 0
stack after
2 4
answer after
7 9 0 8 0 4 4 0 0 0 0
stack 현재 상태
2 4 7
index : 8
value : 10
stack top (position): 7
value : 4
오큰수 후보 발견, 답안 업데이트
stack before
2 4 7
answer before
7 9 0 8 0 4 4 0 0 0 0
stack after
2 4
answer after
7 9 0 8 0 4 4 10 0 0 0
오큰수 후보 발견, 답안 업데이트
stack before
2 4
answer before
7 9 0 8 0 4 4 10 0 0 0
stack after
2
answer after
7 9 0 8 10 4 4 10 0 0 0
오큰수 후보 발견, 답안 업데이트
stack before
2
answer before
7 9 0 8 10 4 4 10 0 0 0
stack after
answer after
7 9 10 8 10 4 4 10 0 0 0
stack 현재 상태
8
index : 9
value : 3
stack top (position): 8
value : 10
stack 현재 상태
8 9
index : 10
value : 10
stack top (position): 9
value : 3
오큰수 후보 발견, 답안 업데이트
stack before
8 9
answer before
7 9 10 8 10 4 4 10 0 0 0
stack after
8
answer after
7 9 10 8 10 4 4 10 0 10 0
stack 현재 상태
8 10
7 9 10 8 10 4 4 10 -1 10 -1
순서대로 따라가다 보면 이해가 될 것이다. 최종적으로 stack에 남는 값은, 맨 마지막 값까지 보았는대도 오큰수를 찾을 수 없었던, 인덱스 들이다. 오큰수를 찾지 못한 녀석들을 마지막으로 -1로 업데이트하면 끝난다.
Code
//
// main.cpp
// algorithm_prac
//
// Created by 최완식 on 2021/04/05.
//
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// stack에 위치 정보를 넣으면 중복 연산을 줄일 수 있다..!!!!
int N;
int a[1000001] = {0,};
int v[1000001] = {0,};
vector<int> s;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a[i];
}
for (int i = 0; i < N; i++) {
cout << "index : " << i << '\n';
cout << "value : " << a[i] << '\n';
if (!s.empty()) {
cout << "stack top (position): " << s.back() << '\n';
cout << "value : " << a[s.back()] << '\n';
}
while (!s.empty() && a[s.back()] < a[i]) {
cout << " 오큰수 후보 발견, 답안 업데이트" << '\n';
cout << " stack before" << '\n' << " ";
for (int j = 0; j < s.size(); j++) {
cout << s[j] << " ";
}cout << '\n';
cout << " answer before" << '\n' << " ";
for (int j = 0; j < N; j++) {
cout << v[j] << " ";
}cout << '\n';
v[s.back()] = a[i];
s.pop_back();
cout << " stack after" << '\n' << " ";
for (int j = 0; j < s.size(); j++) {
cout << s[j] << " ";
}cout << '\n';
cout << " answer after" << '\n' << " ";
for (int j = 0; j < N; j++) {
cout << v[j] << " ";
}cout << '\n';
}
s.push_back(i);
cout << "stack 현재 상태" << '\n';
for (int j = 0; j < s.size(); j++) {
cout << s[j] << " ";
}cout << '\n' << '\n';
}
while (!s.empty()) {
v[s.back()] = -1;
s.pop_back();
}
for (int i = 0; i < N; i++) {
cout << v[i] << " ";
}
return 0;
}