백준 3015 - 오아시스 재결합
백준 3015 - 오아시스 재결합https://www.acmicpc.net/problem/1920 문제 해설입력되는 값이 총 50만개이다. 이 문제는 O(N) or O(NlogN)의 시간복잡도를 갖고 해결을 해야하는 문제이다. 현재 값을 이전 값과 비교해가면서 문제를 해결 하는 방식이다. 스택의 역할은 서로불 수 있는 값의 쌍을 저장하기 위한 역할을 한다. 스택내의 값은 점점 작은 값이 추가 되야 한다. 들어오는 값이 top보다 클 경우 들어오는 값보다 큰 값이 나타날 때까지 pop을 진행하면서 pop을 진행할 때 해당 인원수 만큼 값을 더해준다. 같은 값이 들어올 경우을 어떻게 해결하는 것이 이 문제의 어려운 점이다. 자료구조 pair를 이용한다. first에는 사람의 키를 second에는 같은 키인 사람의 수를 저장한다. 키가 같은 사람이 들어올 경우 같은 키를 갖는 사람만큼 값을 추가해주고 사람수를 + 1 해주고 해당 키를 다시 push해준다. 소스 코드#include <bits/stdc++.h>using namespace std;long long solution(vector<int> heights) { stack<pair<int, int>> st; long long result = 0; for (int heightsIndex = 0; heightsIndex < heights.size(); heightsIndex++) { int height = heights[heightsIndex]; while (!st.empty() && height > st.top().first) { result += st.top().second; st.pop(); } if (!st.empty()) { if (st.top().first == height) { pair<int, int> temp = st.top(); st.pop(); result += temp.second; if (!st.empty()) { result += 1; } st.push({height, temp.second + 1}); } else { result += 1; st.push({height, 1}); } } else { st.push({height, 1}); } } return result;}int main(void) { int numOfPeople; vector<int> heights; cin >> numOfPeople; for (int peopleIndex = 0; peopleIndex < numOfPeople; peopleIndex++) { int height; cin >> height; heights.push_back(height); } cout << solution(heights) << '\n'; return 0;}