[백준] 12033번 김인천씨의 식료품가게 (Small) (C++)

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

 

 

이 문제는 N개의 물품이 주어지고 2 X N개의 정상가와 할인가가 포함된 가격들이 입력된다.

 

이때 N개의 할인가를 오름차순으로 출력하는 문제이다.

 

 

N개의 할인가를 출력하기 위해서 입력된 가격들을 해시 테이블에 저장하였다.

이때 값을 꺼내면서 할인된 가격을 계산하여 할인된 가격이 양수인경우 기록된 해시테이블에서

정상가와 할인가를 1씩 낮추며 값을 출력하였다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int T, N;
int cnt = 1;

void solve(vector<ll> &arr, map<ll, ll> &m) {
    for(auto &it : arr) {
        if(m[it] == 0) continue;
        ll tmp = it * 4 / 3;

        if(m[tmp] > 0) {
            m[it]--;
            m[tmp]--;
            cout << it << " ";
        }
    }
    cout << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N;

        vector<ll> v(2 * N);
        map<ll, ll> m;

        for(auto &it : v) {
            cin >> it;
            m[it]++;
        }

        cout << "Case #" << cnt++ << ": ";
        solve(v, m);
    }
}

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

    input();
}