문제링크
https://www.acmicpc.net/problem/17298
문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 512MB
해설
비교하고자 하는 원소값의 오른쪽에서 구하고자 하는 값을 찾을 수 있기 때문에, 수열의 끝에서부터 시작점으로 거꾸로 스택을 쌓으며 계산하는 방법을 사용한다. 스택에는 내림차순을 유지하면 값을 쌓아나간다.
풀이
먼저 스택에 inf 값(1000001)을 push하여, -1을 출력하기 위해 비교할 가장 큰 값을 만들어둔다.
입력값을 뒤에서부터 하나씩 스택에 넣어준다. 만약 stack.back()이 해당 원소보다 크다면 answer에 back()의 값을 넣고 입력 값을 그대로 push한다. 반대로 해당 원소보다 작다면 원소보다 큰 값이 나올 때 까지 stack.pop_back()을 반복한다. 뒤에 나올 원소에서 값을 비교할 때는 작은 값들이 불필요하기 때문에, 이를 pop해주어 시간과 공간을 아낄 수 있다. 그 후 back()의 값을 answer에 넣고 입력값을 push한다. 이를 코드로 옮기면 아래와 같다.
stack.push_back(1000001);
for(int i = A-1; i >= 0; i--) {
while(stack.back() <= NGE[i]) {
stack.pop_back();
}
answer[i] = (1000001 == stack.back())? -1:stack.back();
stack.push_back(NGE[i]);
}
answer를 그대로 출력하면 원하는 결과를 얻을 수 있다.
코멘트
조금 더 시간을 아끼는 방법을 찾았어야 했는데... 필요없는 값을 pop 해야한다는 건 기억했는데, pop하는 대상을 찾는게 쉽지않았던 것 같다.
고민
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int A;
cin >> A;
vector<int> NGE(A);
vector<int> stack;
vector<int> index;
if(A == 1) {
cin >> NGE[0];
cout << "-1";
return 0;
}
// initiate Value
int indexIndex = 0;
for(int i = 0; i < A; i++) {
cin >> NGE[i];
}
for(int i = A-1; i >= 1; i--) {
if(NGE[i-1] < NGE[i]) {
stack.push_back(NGE[i]);
index.push_back(i);
}
}
if(stack.empty()) {
for(int i = 0; i < A; i++) {
NGE[i] = -1;
}
} else {
for(int i = 0; i < A; i++) {
if(i == index.back()) {
stack.pop_back();
index.pop_back();
}
int temp = -1;
for(int j = stack.size()-1; j >= 0; j--) {
if(NGE[i] < stack[j]) {
temp = stack[j];
break;
}
}
NGE[i] = temp;
}
}
for(auto x : NGE) {
cout << x << " ";
}
cout << '\n';
return 0;
}코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int A;
cin >> A;
vector<int> NGE(A);
vector<int> stack;
vector<int> answer(A);
for(int i = 0; i < A; i++) {
cin >> NGE[i];
}
stack.push_back(1000001);
for(int i = A-1; i >= 0; i--) {
while(stack.back() <= NGE[i]) {
stack.pop_back();
}
answer[i] = (1000001 == stack.back())? -1:stack.back();
stack.push_back(NGE[i]);
}
for(auto x : answer) {
cout << x << " ";
}
cout << '\n';
return 0;
}
Uploaded by Notion2Tistory v1.1.0