크기가 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;
}
#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해주었다.
여기서 또 한가지의 포인트는 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>> 형태로 사용하면 된다.
이렇게 무사히 스택의 특징을 이용하여 시간제한을 극뽁하고 문제를 해결할 수 있었다. 계속해서 스택을 이용하는 문제를 풀다보니 이제 어느 경우에 스택을 사용하고, 어떤 특징들을 사용하는지 사알짝 감이 오는 것 같기도 하고?? 😋 아직 많이 부족하지만 예전에 비하면 확실히 생각하는 방법이나 문제에 접근하는 방법을 알아가는 것 같아서 좋다. 더 열심히 해서 더 많이 성장할 수 있기를!! 빠이링 해야지~💪