머리를 아무리 굴려도 도저히 올바른 솔루션이 생각이 안나서 다른 분의 풀이를 찾아보고 어떻게 풀었는지 보고 아 이렇게 푸는거였네.. 하고 풀어본 문제..
골드4 문제라 어려웠구나...ㅠㅠ
처음에는 deque와 stack으로 풀려고 했는데 테스트 케이스 몇개만 통과하는 잘못된 코드라서 처음부터 다시 짜기 시작했다.
솔루션 찾아보고 푼 코드는 다음과 같다.
풀이 코드
#include <bits/stdc++.h>
using namespace std;
int arr[1000004];
int ret[1000004];
stack<int> stk;
int N;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
fill(&ret[0], &ret[0] + 1000004, -1);
for(int i = 0; i < N; i++){
cin >> arr[i];
while( stk.size() && arr[i] > arr[stk.top()]){
ret[stk.top()] = arr[i];
stk.pop();
}
stk.push(i);
}
for(int i = 0; i < N; i++){
cout << ret[i] << " ";
}
return 0;
}오큰수는 오른쪽에 있어야 하기 때문에 결국 맨 마지막 숫자는 -1이 반환될 것이다.
맨 첫번째 숫자가 가장 큰 경우에도 맨 첫번째에 -1 을 출력해야 하므로 출력할 배열을 -1로 전체 초기화를 시켜주었다.
그리고 for문을 돌면서 input을 받고 현재 스택이 비어있는 경우에 push, 현재 스택이 비어있지 않지만 이전에 등장한 숫자보다 작은 경우에도 push한다.
스택을 살펴보면 arr[i]가 아닌, for문의 현재 i값을 push 하고 있는 것을 볼 수 있다.
처음 풀 때는 스택에 그냥 입력받은 값을 바로 push 했었는데 이 경우에는 결국 값의 위치를 알 방법이 없어서 이중 for문을 사용한 시간초과 코드로 풀어야 하는 것을 깨닫고 스택에는 현재 등장한 숫자의 인덱스를 push 해야 함을 알게 되었다.
등장한 숫자를 계속해서 arr 배열에 순서대로 저장해놓았기 때문에 스택의 top의 값을 arr[stk.top()]을 통해 찾아낼 수 있다.
여러 차례 비교(스택을 계속 pop)를 해야할 수 있으므로 while문을 사용해서 반복 시켜주어야 한다.
그리고 결과 값도 마찬가지로 순서대로 출력해주어야 하므로 stk.top()을 사용해서 ret 배열의 인덱스 위치를 잡아주어야 했다.
솔루션을 보고 한번 풀었던 것을 다시 풀어본 문제라서 아직 내 기억 메모리가 푸는 방법을 기억하고 있는 것 같다. 잊혀질 쯤에 다시 풀어볼 문제..!
