문제
크기가 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이다.
첫 번째 코드 (38% 시간초과)
#include <iostream>
#include <stack>
using namespace std;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
int input;
stack<int> st;
stack<int> less;
cin >> n;
int arr[n];
for(int i = 0 ; i < n ; i++){
cin >> arr[i];
}
for(int i = n-1 ; i >=0 ; i--){
st.push(arr[i]);
}
for(int i = 0 ; i < n ; i++){
int cur = arr[i];
st.pop();
if(st.empty()){
cout << "-1 ";
continue;
}
while(!st.empty()){
if(cur < st.top()){
cout << st.top() <<" ";
while(!less.empty()){
st.push(less.top());
less.pop();
}
break;
}else{
less.push(st.top());
st.pop();
if(st.empty()){
cout << "-1 ";
while(!less.empty()){
st.push(less.top());
less.pop();
}
break;
}
}
}
}
return 0;
}
골드 4, 시간제한 1초, N 100만 에서 시간복잡도를 신경써야하는 문제임을 알 수 있었다...
처음에 짠 코드는 스택 두개와 입력받은 수열 배열을 만들어놓고, 수열의 맨 왼쪽부터 체크해서
수열이 3 5 2 7 이면 스택 하나에는 3 5 2 7 이렇게 넣어놓고 시작했다.
현재 원소가 3이면, 먼저 스택의 맨 위(=자기 자신)를 pop 한 다음 (5 2 7)
자신보다 작으면 less 스택에 넣고, 자신보다 크면 출력 후 less 배열 원소들을 다시 stack으로 넣어서 복구 시켜줬다.
왼쪽부터 시작하는 게 왼쪽에 있는 가장 큰 수를 빨리 찾을 수 있을거라 생각하고 알고리즘을 짰지만
스택 두 개를 두고 매 경우마다 복구시켜주면서 for과 while문이 중첩되었고 역시나 38%에서 시간초과가 났다 ^^;
스택 하나로 해결할 수 있는 방법이 필요했다.
정답 코드
#include <iostream>
#include <stack>
using namespace std;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
int input;
stack<int> st;
cin >> n;
int arr[n];
int ans[n];
for(int i = 0 ; i < n ; i++){
cin >> arr[i];
}
for(int i = n-1 ; i >=0 ; i--){
int cur = arr[i];
if(st.empty()){
ans[i] = -1;
st.push(cur);
continue;
}
if(cur < st.top()){
ans[i] = st.top();
}else{ //스택 위가 나보다 작으면
while(st.top() <= cur){
st.pop();
if(st.empty()) break;
}
if(st.empty()){
ans[i] = -1;
}else{
ans[i] = st.top();
}
}
st.push(cur);
}
for(int i = 0 ; i < n ; i++){
cout << ans[i] << " ";
}
return 0;
}
첫번째 시도때는 모든 원소를 스택에 넣어놓고 하나씩 제거해갔는데,
수열의 오른쪽부터 체크하면서 스택에 원소를 추가하는 식으로 과정이 더 간단해졌다.
수열의 오른쪽부터 체크하면서 스택의 맨 위 원소가 수열보다 크면 출력하고, 작으면 제거하고, 스택이 비었으면 오큰수가 없으므로 -1을 출력한다.
오른쪽에 있는 애들 중, 자기자신보다 크면서 가장 왼쪽에 있는 애를 찾는 문제이기 때문에
오른쪽 -> 왼쪽으로 가면서 자기자신보다 작은 애들은 스택에서 제거하고 다음 차례로 넘기니
매차례 스택을 복구 시켜줬던 첫번째 시도보다 시간도 줄어들고 코드도 깔끔해졌다.
'알고리즘' 카테고리의 다른 글
[C++/백준 2110] 공유기 설치 (0) | 2022.09.14 |
---|---|
[C++/백준 5052] 전화번호 목록 (0) | 2022.09.14 |
[백준/C++] 톱니바퀴 (0) | 2022.03.25 |
[C++/백준 21608] 상어 초등학교 (0) | 2022.03.25 |
[C++/백준 14502] 연구소 (0) | 2022.03.25 |