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)