Algorithm/baekjoon
[BOJ 1655] 가운데를 말해요
식빵민
2022. 7. 30. 17:32
1655번: 가운데를 말해요
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
문제 분석
- 시간제한 : 0.1초 ⇒ Big-O 기준 최대 1,000만 연산
- 다뤄야 하는 수의 갯수 ⇒ 100,000개
- 반복문 사용 불가 (n번 반복하는거 말고)
- 매우 짧은 제한 시간, 적합한 stl을 찾는게 핵심일 듯
- 갯수가 짝수일때는 두 중간값중 작은 값이 답이고, 갯수가 홀수 일때는 중간값을 출력해야 한다.
priority_queue<int>s;//작은 값들 들어가는 maxHeap
priority_queue<int,vector<int>,greater<>>l;//큰 값들 들어가는 minHeap
int n,x,tmp2,tmp;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
s.push(-10001); //첫값이 들어갈 때
l.push(10001);
cin>>n;
while(n--){
cin>>x;
if(s.size()<=l.size()) s.push(x);// 기존에 l이 크거나 같으면 무조건 s에 넣어줌
else l.push(x);
if(s.top()>l.top()){ //pq에 넣은 후 top끼리 비교
// 작은것들중 가장 큰게 큰것들중 가장 작은거 보다 크면
// 둘이 바꿔줘
tmp = s.top();
s.pop();
tmp2 = l.top();
l.pop();
l.push(tmp);
s.push(tmp2);
}
cout<<s.top()<<"\n";
}
return 0;
}
풀이 방식
- <priorty_queue> 사용, 두개의 pq를 만들어 하나는 maxHeap, 하나는 minHeap 으로
- maxHeap에 작은값들, minHeap에 큰값을 넣어 작은값들 중에 가장 큰값(maxHeap.top)을 중간값이 되게 함
- 총 갯수가 홀수일때, maxHeap이 하나 더 많이 들어가게 함으로서 maxHeap.top이 답이되게 통일성을 만들어줌
느낀 점
- 문제를 보면 중간값을 찾는데 logn시간이 넘게 걸리면 안되겠다는 생각이 들었다.
- 이 문제는 pq를 두개 만들라는 힌트를 얻어 풀었는데 그런 힌트를 얻지 못했으면 쉽게 풀지 못했을 거 같다.
- 처음엔 이 경우 저 경우 다따져가며 답을 찾으려고 했다가 "틀렸습니다"가 떴다.
- 그래서 일반화시키니 코드가 간단해지고 스스로에게도 확신하게 됐다.
시간복잡도
- n번 반복
- pq.top에 접근 -> O(1)
- pq.pop,pq.push -> O(logn)
➣ O(nlogn)