[BOJ 1655] 가운데를 말해요

1655번: 가운데를 말해요

문제 분석

• 시간제한 : 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)