취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 32963번 문제인 맛있는 사과이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/32963

먼저 사과의 나열 순서와 답은 상관관계가 없으므로 주어진 사과를 크기순으로 정렬해도 답이 변하지 않음을 관찰하자. 그리고 사과를 크기순으로 정렬하자.

다음으로, 큰 사과부터 차례대로 보면서 가장 큰 사과의 크기가 얼마인지, 그 크기의 사과가 몇개인지를 두 변수를 활용해 관리하고, 크기 역순으로 해당 사과까지 확인했을 때의 문제의 답이 무엇인지를 잘 기록해두자.

이제 각 쿼리로 주어진 수에 대하여 해당 수보다 크거나 같은 사과 중 가장 인덱스가 작은 사과부터 마지막 사과까지의 사과 중 가장 큰 사과의 개수가 몇 개인지 앞서 구한 배열을 이용해 답하는 것으로 문제를 해결할 수 있다. 이러한 인덱스는 이진 탐색으로 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, Q, mx = -1, cnt = 0;
pair<int, int> P[200000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> Q;
    for (int i = 0; i < N; i++) cin >> P[i].first;
    for (int i = 0; i < N; i++) cin >> P[i].second;

    sort(P, P + N);
    for (int i = N - 1; i > -1; i--) {
        if (P[i].second > mx) mx = P[i].second, cnt = 1;
        else if (P[i].second == mx) cnt++;
        P[i].second = cnt;
    }

    while (Q--) {
        int K, L = 0, R = N - 1; cin >> K;
        if (P[N - 1].first < K) cout << 0 << '\n';
        else {
            while (L < R) {
                int mid = (L + R) / 2;
                if (P[mid].first < K) L = mid + 1;
                else R = mid;
            }
            cout << P[L].second << '\n';
        }
    }
}