✍ 문제
크기가 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)을 공백으로 구분해 출력한다.
✅ 코드
❗ 시간 초과 코드 (벡터+단순 반복)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int num;
cin >> num;
vector<int> nge;
vector<int> result;
for (int i = 0; i < num; i++) {
int number;
cin >> number;
nge.push_back(number);
}
for (int i = 0; i < num - 1; i++) {
for (int j = i + 1; j < num; j++) {
if (nge[i] < nge[j]) {
result.push_back(nge[j]);
break;
}
}
if (result.size() != i + 1) result.push_back(-1);
}
result.push_back(-1);
for (int i = 0;i < result.size();i++) {
cout << result[i] << ' ';
}
return 0;
}❗ 정답 코드 (stack, pair)
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tc;
stack<pair<int, int>> input_st;
cin >> tc;
vector<int> result(tc, -1);
for (int i = 0; i < tc; i++) {
int num;
cin >> num;
while (!input_st.empty() && input_st.top().first < num) {
result[input_st.top().second] = num;
input_st.pop();
}
input_st.push(make_pair(num, i));
}
for (int i = 0; i < tc; i++) {
cout << result[i] << ' ';
}
vector<int>().swap(result); //메모리 해제
return 0;
}
✅ 코드풀이
처음 17298번을 보고 solved.ac 난이도가 골드4이길래, 쫄고 시작했는데 너무 금방 풀어버려서 오잉 뭐지? 하는 찰나에 시간초과를 맞이했다🤕 (아직도 난이도 골드에도 쪼는 나...)
처음에는 단순히 입력값을 vector로 받고, 자신보다 오른쪽에 있는 원소들을 탐색하다가 자신의 값보다 큰 원소를 만나면 그 값을 result vector에 저장하는 방식으로 코드를 짰다. 제출을 해보니 시간초과가 뜨길래 살며시 알고리즘 분류가 스택으로 되어 있는 것을 확인하고는 다시 머리를 굴리기 시작했다.
이 문제는 지난 포스팅에서 다루었던 후위 표기식와 매우 유사한 문제 풀이 구조를 가지고 있었다. 스택에 입력값을 저장하면서 일정 기준이 만족되거나 만족되지 않았을 때 취할 액션만 정해주면 끝이다.
❗ 알고리즘
오큰수는 자신보다 오른쪽에 있는 큰 수들 중 가장 왼쪽에 있는 수이다. 따라서 stack에 값을 저장하면서 stack의 top보다 큰 수가 들어오려고 하는 경우, 그 수가 stack top의 오큰수가 되는 것이다. 오큰수를 저장하기 위한 자료구조로는 vector를 선택하였고 모든 값을 -1로 초기화 시켜놓았다. 오큰수가 없는 경우는 -1을 출력해야하기 떄문이다.
while (!input_st.empty() && input_st.top().first < num)
위와 같은 반복문 조건을 통해 stack의 top이 input 값(num) 보다 작은 경우는 num값을 vector [stack top의 index]에 저장하고 해당 top값을 pop해주었다.
❗ pair
여기서 또 한가지의 포인트는 stack에 입력값을 저장해줄 때 pair 클래스를 이용하여 (입력값, index) 형태로 저장했다는 것이다. 특정 원소의 오큰수를 구한 후, result vector의 올바른 index에 넣어주어야 하기 때문에 index의 값도 함께 저장한 것이다. 그리고 서로 연관된 두 가지 값을 동시에 다루기 위해서는 pair가 가장 적당할 것이라고 생각했다.
-
pair의 사용
pair는 utility 헤더파일에 포함된 STL이다. utility 헤더파일은 algorithm, vector 헤더파일에 이미 포함되어 있기 때문에 algo나 vector 헤더파일을 이미 선언했다면 중복하여 선언하지 않아도 된다. -
pair <type1, type2> p;
p.first : p의 첫번째 인자 반환
p.second : p의 두번째 인자 반환
-
값 저장하기
1) p.first = 1;
p.second = 2;2) make_pair (1, 2);
스택에 pair를 저장하고 싶은 경우, stack<pair<type1, type2>> 형태로 사용하면 된다.
이렇게 무사히 스택의 특징을 이용하여 시간제한을 극뽁하고 문제를 해결할 수 있었다. 계속해서 스택을 이용하는 문제를 풀다보니 이제 어느 경우에 스택을 사용하고, 어떤 특징들을 사용하는지 사알짝 감이 오는 것 같기도 하고?? 😋 아직 많이 부족하지만 예전에 비하면 확실히 생각하는 방법이나 문제에 접근하는 방법을 알아가는 것 같아서 좋다. 더 열심히 해서 더 많이 성장할 수 있기를!! 빠이링 해야지~💪
