[Silver V] 김인천씨의 식료품가게 (Small) - 12033

[문제 위치]

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

[문제 풀이]

이 문제는 그리디(빈도맵) 를 통해 해결하는 문제이다.
모든 물건은 정상가 4k와 할인가 3k 한 쌍을 이루고, 인쇄물 더미는 전체가 오름차순으로 정렬되어 있으므로 아직 짝지어지지 않은 가장 작은 값은 반드시 할인가(3k)이다. 따라서 배열을 정렬된 그대로 훑으면서 아직 남아있는 가장 작은 값 x를 할인가로 선택하고 짝값 y=x/3*4(=4k)를 빈도맵에서 1개 소모하는 과정을 반복하면 오름차순으로 할인가들만 골라낼 수 있게 해결한다
아래는 이를 구현한 코드이다.

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FASTIO;
    int T;
    if (!(cin >> T)) return 0;
    for (int tc = 1; tc <= T; ++tc) {
        int N; 
        cin >> N;
        vector<long long> a(2 * N);
        for (int i = 0; i < 2 * N; ++i) cin >> a[i];

        // a는 이미 오름차순. 빈도맵으로 사용/소모 관리
        unordered_map<long long, int> cnt;
        cnt.reserve(2 * N * 2);
        for (auto v : a) ++cnt[v];

        vector<long long> disc; 
        disc.reserve(N);

        for (long long x : a) {
            if (cnt[x] == 0) continue;     // 이미 소모된 값
            // x는 현재 남아있는 최솟값이므로 반드시 할인가(3k)
            --cnt[x];
            long long y4 = x * 4;          // 짝은 y = 4/3 * x
            // 문제 조건상 항상 나누어떨어지고 존재함
            long long y = y4 / 3;
            --cnt[y];
            disc.push_back(x);
        }

        cout << "Case #" << tc << ":";
        for (long long v : disc) cout << ' ' << v;
        cout << '\n';
    }
    return 0;
}