[자바] 백준 12034 - 김인천씨의 식료품가게 (Large) (boj java)

문제 : boj12034

 

  정상가와, 정상가의 75%인 할인가가 n 쌍 존재한다. 그리고 문제 조건으로 '정답은 단 하나만 존재하는것이 보장되어 있음'라고 했으므로 정답을 찾으려면 단순히 생각해서 모든 경우를 살펴봐서 그 중 모든 정상가-할인가 쌍이 맞아떨어지는 경우를 찾으면 될 것이다. 하지만 잘 생각해보면 결국 할인가는 정상가보다 언제나 클 것이다. 따라서 주어진 값들 중 가장 큰 값은 할인가가 될 수 없으며 무조건 정상가이다. 따라서, 큰 값부터 정상가로 생각해 할인가를 찾아나갈 경우, 매번 남은 값들 중 가장 큰 값은 정상가일 수 밖에 없다.

 

  정리하자면 오름차순으로 입력이 들어오므로, 마지막 값부터 시작해서 점차적으로 내려오면서 아직 존재하는 값이라면 무조건 정상가이고, 해당 값과 그 할인가를 제외한다. 이걸 모든 값이 제거될 때 까지 반복해주면 된다.

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= t; tc++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] arr = new int[n*2];
            HashMap<Integer, Integer> hm = new HashMap<>();
            for (int i = 0; i < 2*n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                hm.put(arr[i], hm.getOrDefault(arr[i], 0)+1);
            }
            ArrayList<Integer> answer = new ArrayList<>();
            for (int i = 2*n-1; i >= 1; i--) {
                int cur = arr[i];
                if (hm.get(cur) == 0) continue;
                hm.put(cur, hm.get(cur)-1);
                int salePrice = cur-cur/4;
                answer.add(salePrice);
                hm.put(salePrice, hm.get(salePrice)-1);
            }
            sb.append(String.format("Case #%d: ", tc));
            for (int i = n-1; i >= 0; i--) sb.append(answer.get(i)).append(' ');
            sb.append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}