로직 자체는 크게 어렵지 않을 거 같았는데 정답률이 많이 낮아 의아해하다가 시간 초과로 한번 틀린 후 꽤 어려운 문제라는 걸 알았습니다. 혼자 고민을 좀 해보다 힌트를 조금 찾아본 후 풀었는데, 쉽지 않았던 문제였습니다. 예제 입력으로 먼저 예를 들어 보면 스택에 3, 5, 2, 7이 push되어 있는 상태입니다. 각 인덱스 0, 1, 2, 3의 오큰수를 찾아야하는데 인덱스를 저장할 벡터를 하나 더 만든 후 오큰수를 찾게 되면 해당 인덱스는 pop시켜 버립니다. 인덱스 벡터에 0을 push하고 0번인 3을 제외한 5, 2, 7과 비교합니다. 0번인 3은 5보다 작기에 5는 3의 오큰수가 됩니다. 그렇게 되면 0번의 오큰수는 찾았기에 0을 pop시킵니다. 다음은 1번인 5의 차례입니다. 5는 2보다 크기에 1번을 pop시키지 않고 다음 인덱스인 2번을 push합니다. 2번인 2는 7보다 작기 때문에 오큰수가 됩니다. 그럼 2번을 pop하게 됩니다. 인덱스 벡터에는 현재 1이 남아있고 1번인 5또한 7보다 작기 때문에 오큰수가 7이 됩니다. 즉 인덱스 번호를 push하며 인덱스 번호를 모두 돌며 오큰수를 찾으면 해당 인덱스를 pop하여 지우고 해당 과정을 마지막까지 반복합니다. 아래는 해당 과정을 표로 나타낸 것입니다. 만약 마지막까지 오큰수를 찾지 못한 경우 -1로 채워주면 됩니다.
스택
3
5
2
7
인덱스 벡터
0
비교
스택[0] < 5 : TRUE
오큰수
5
스택
3
5
2
7
인덱스 벡터
pop
1
비교
스택[1] < 2 : FALSE
오큰수
5
?
스택
3
5
2
7
인덱스 벡터
pop
1
2
비교
스택[2] < 7 : TRUE
오큰수
5
?
7
스택
3
5
2
7
인덱스 벡터
pop
1
pop
비교
스택[1] < 7 : TRUE
오큰수
5
7
7
스택
3
5
2
7
인덱스 벡터
pop
pop
pop
3
비교
스택[3] < 7 : FALSE
오큰수
5
7
7
-1
#include<iostream>
#include<vector>
using namespace std;
int res[1000001];
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n; cin >> n;
vector<int> stack(n);
for (int i = 0; i < n; i++) cin >> stack[i];
vector<int> index;
vector<int> res(n);
index.push_back(0);
for (int i = 1; i < n; i++) {
if (index.empty()) {
index.push_back(i);
}
else {
while (!index.empty() && stack[index.back()] < stack[i]) {
res[index.back()] = stack[i];
index.pop_back();
}
index.push_back(i);
}
}
for (int i = 0; i < n; i++) {
if (res[i] == 0) cout << "-1 ";
else cout << res[i] << " ";
}
return 0;
}
댓글