이번에는 백준 3015번 오아시스 재결합 문제를 풀어보았습니다.
처음에는 각 사람마다 왼쪽 사람들을 모두 확인하는 방식으로 생각했지만, 사람의 수가 최대 500,000명이므로 O(N²)으로는 해결할 수 없었습니다.
이후 현재 사람보다 작거나 같은 사람들은 다시 확인할 필요가 없다는 점을 이용하여 스택으로 해결하였습니다.
또한 같은 키가 여러 명 연속해서 등장할 수 있기 때문에 같은 키의 개수를 함께 저장하도록 구현하였습니다.
문제 설명
두 사람이 서로 볼 수 있으려면 두 사람 사이에 두 사람보다 키가 큰 사람이 없어야 합니다.
줄에 서 있는 사람들의 키가 주어질 때, 서로 볼 수 있는 사람 쌍의 개수를 구하는 문제입니다.
풀이 아이디어
왼쪽에서 오른쪽으로 사람을 한 명씩 확인하였습니다.
스택에는 현재 사람보다 큰 사람들만 남도록 관리하였습니다.
현재 사람보다 키가 작거나 같은 사람은 현재 사람과 서로 볼 수 있으므로 스택에서 제거하였습니다.
같은 키는 여러 명이 연속될 수 있기 때문에 (키, 개수) 형태로 압축하여 저장하였습니다.
모든 사람을 처리하면서 서로 볼 수 있는 쌍의 개수를 계산하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int n;
long long int ret, temp;
stack<pair<long long int, long long int>> s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
int cnt = 1;
while (s.size() && s.top().first <= temp) {
ret += s.top().second;
if (s.top().first == temp) {
cnt = s.top().second + 1;
} else {
cnt = 1;
}
s.pop();
}
if (s.size())
ret++;
s.push({temp,cnt});
}
cout << ret << '\n';
return 0;
}풀이 흐름
- 사람을 왼쪽부터 차례대로 확인합니다.
- 현재 사람보다 작거나 같은 사람을 스택에서 제거합니다.
- 제거되는 사람들은 현재 사람과 서로 볼 수 있으므로 정답을 증가시킵니다.
- 같은 키는 개수를 합쳐 관리합니다.
- 스택에 사람이 남아 있다면 가장 가까운 큰 사람 한 명과도 서로 볼 수 있습니다.
- 현재 사람을 스택에 넣습니다.
- 모든 사람을 처리한 뒤 정답을 출력합니다.
구현 포인트
1. (키, 개수) 형태로 저장
스택에는 단순히 키만 저장하지 않고 같은 키의 개수도 함께 저장하였습니다.
stack<pair<long long int, long long int>> s;first: 키second: 같은 키의 개수
같은 키가 여러 명 연속해서 등장하는 경우를 한 번에 처리하기 위해 사용하였습니다.
2. 현재 사람보다 작거나 같은 사람 제거
현재 사람보다 키가 작거나 같은 사람은 앞으로 다시 확인할 필요가 없습니다.
while (s.size() && s.top().first <= temp)이 사람들은 모두 현재 사람과 서로 볼 수 있습니다.
ret += s.top().second;같은 키가 여러 명 압축되어 있을 수 있기 때문에 개수만큼 더해주었습니다.
3. 같은 키 처리
현재 사람과 같은 키라면 개수를 합쳐 저장하였습니다.
if (s.top().first == temp) {
cnt = s.top().second + 1;
}예를 들어
5 5 5가 들어오면
(5,3)처럼 하나의 원소로 관리하도록 구현하였습니다.
4. 더 큰 사람 한 명 처리
작거나 같은 사람을 모두 제거한 뒤에도 스택이 남아 있다면,
남아 있는 top은 현재 사람보다 큰 사람 중 가장 가까운 사람입니다.
if (s.size())
ret++;현재 사람은 이 사람 한 명과만 서로 볼 수 있습니다.
5. 현재 사람 저장
현재 사람을 스택에 넣었습니다.
s.push({temp, cnt});- 같은 키가 있었다면 기존 개수에 1을 더한 값을 저장합니다.
- 그렇지 않다면
cnt = 1인 상태로 저장합니다.
이 과정을 반복하면 스택에는 현재 위치 기준 왼쪽 사람들 중 아직 볼 수 있는 후보들만 남게 됩니다.
