이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 91 번째 글 입니다.
목차
골드1 : stack 문제이다.
생각
아, 어려웠다.. 처음에 dp로 풀생각을 했더니, $O(n^2)$ 이라 500,000인 input에 맞지 않는다. 또한 그 과정에서 세그먼트 트리 혹은 우선 순위 큐를 사용하려 했지만 구현 난이도가 올라가 고민했다.
역시 알고리즘 문제는 약간은 컴퓨터 처럼 순차적으로 규칙을 찾는 것이 가장 중요하다는 생각을 한다. 또한, 어떠한 자료구조를 사용하여 문제의 input을 어떠한 규칙을 갖는 무언가를 만드는 것이 매우 중요하다.
해당 문제에서 핵심은, i번째 사람의 입장에서 앞을 보았을 때, 보이는 모습을 상상해보는 것이 중요하다. 이를 상상해보면 그 사람은 계속 사람의 키가 올라가는 모양으로 보인다. 이는 index 0에서 부터 생각해 볼때, i까지의 위치까지 감소하는 수열을 갖고 있는다고 생각할 수 있다. 이런 감소하는 수열을 갖고 있다면, i+1 번째의 감소하는 수열을 만드는 과정에서 답안을 도출할 수 있다.
물론, 이 문제는 키가 같을 수 있다는 점에서 이를 처리하는 방법이 필요하다. 이를 해결하는 방법은 역시나 i번째 사람의 입장에서 앞을 보았을 때, 어떤 식으로 pair가 구성되는지 시뮬레이션 하는 것이 도움이 된다.
Code
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <string.h>
using namespace std;
int N;
vector<pair<int, int>> line;
long long ans = 0; // 답의 개수가 무지하게 많이 나오니 이거 꼭 체크!
void print(){
for (int i = 0; i < int(line.size()); i++) {
cout << line[i].first << " ";
}cout << '\n';
for (int i = 0; i < int(line.size()); i++) {
cout << line[i].second << " ";
}cout << '\n' << '\n';
}
int main(){
cin >> N;
for (int i = 0; i < N; i++) {
int nowH;
cin >> nowH;
bool same = false;
// 감소하는 수열을 만들며 규칙에 따라 답을 업데이트한다.
while(!line.empty()){
pair<int, int> near = line.back();
// 현재 키가 가장 근방에 있는 사람보다 클 경우
if (nowH > near.first) {
// 감소하는 수열을 만들어 놓은 상태이기 때문에
// 이 사람은 나와 쌍이 될 수 있다.
ans += near.second;
line.pop_back(); // 답을 추가했으니 뺀다.
} // 현재 키가 가장 근방에 있는 사람보다 작을 경우
else if (nowH < near.first) {
// 이 사람까지 답에 추가할 수 있다. 같은 키를 다 넣을 수는 없고
// 딱 마지막 사람만 가능하다!!!
// 추가하고 나서는 while문을 탈출한다.
ans += 1;
break;
} // 현재 키가 가장 근방에 있는 사람과 같을 경우
else {
// 같은 키를 가진 사람은 답에 추가가능하다.
ans += near.second;
// 현재 가장 뒤에 있는 사람을 빼온다.
int count = near.second;
line.pop_back();
// 뺀뒤에도 비어있지 않다는 얘기는 현재 같은 키 말고 큰 키를 가진 사람이 앞에 있다는 얘기이다.
// 가장 근방에 있는 사람까지 pair가 가능하다.
if (!line.empty()) {
ans += 1;
}
// 지금 있는 사람의 count 정보에 +1 하여 다시 넣어준다.
line.push_back(make_pair(nowH, count+1));
// 이미 내 현재 높이가 앞 높이와 같으므로 이것보다 작은 키는 나올 수 없다.
same = true;
break;
}
}
// 기존의 line을 업데이트한 후에, 현재 사람의 정보를 추가한다.
if (!same) {
line.push_back(make_pair(nowH, 1));
}
// cout << ans << '\n';
// print();
}
cout << ans;
return 0;
}