[C++] 백준(BOJ) - 3015 : 오아시스 재결합
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.
사람들이 서 있는 순서대로 입력이 주어진다.
출력
서로 볼 수 있는 쌍의 수를 출력한다.
알고리즘
- 스택
풀이
- 쌍의 수 - Stack
- A와 B가 짝을 지을 수 있는지만 생각한다.
- 큰 키만을 Stack에 남겨서 정답이 되는 쌍의 수를 카운팅 한다.
- n의 유효 범위가 50만. 50만 X 50만 => 정수 범위를 넘어선다
- long long 형을 사용한다.
- 같은 키가 오는 경우를 고려한다.
- 같은 키도 쌍을 지을 수 있는 것을 고려한다면 같은 키를 가진 사람의 수를 카운팅 하는 변수를 하나 더 선언해야 한다.
코드
// BOJ-3015 : 오아시스 재결합
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, res, tmp;
stack<pair<ll, ll>> stk; // first에는 키를 second에는 현재 스택에 같은 키를 가진 사람의 수를 기록
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> tmp;
int cnt = 1; // 동일한 키의 사람의 수를 카운팅
while (stk.size() && stk.top().first <= tmp) // 현재 사람의 키가 스택의 top보다 크다 (오름차순 체크)
{
res += stk.top().second;
if (stk.top().first == tmp) // 동일한 키의 사람이 들어올 경우 카운트를 하나씩 증가시켜 저장
{
cnt = stk.top().second + 1;
}
else cnt = 1;
stk.pop(); // 현재 사람의 키보다 작은 것들은 모두 스택에서 제거 (더이상 스택에 담겨있을 이유가 없다)
}
if (stk.size()) res++; // 현재 체크하는 키가 원래 있던 스택에 존재하는 키보다 작은 경우 (내림차순 체크)
stk.push({ tmp, cnt });
}
cout << res << '\n';
return 0;
}
평가
- Stack을 활용해서 짝짓기 하는 문제 중 난이도가 조금 있는 문제이다.
- 쌍의 수를 세는 것과 같은 키를 가진 사람의 수를 카운팅하여서 연산을 따로 처리해주어야 하는 연산이 더해져있다.
