Swea 19113. 식료품 가게 D3 - 자바 구현

할인 해!

 

 

 

열어분 덕분입니다 호호

 

 

문제에 오류가 있어서 해결이 안된 문제다. 댓글에 109 -> 10^9를 봤어야했는딩..

댓글 덕분에 해결 ^<^

 

일단 1~100개의 물건이 존재하고, 해당 물건의 기존 가격과 25%할인 한 가격이 오름차순으로 주어진다.

이 섞여진 가격 속에서 기존 원 가격을 찾으면 되는 문제이다.

 

오름차순으로 정렬이 되어 있으며 예시를 만들어 보았다.

 

따란

 

다 섞여버렸자나..

 

원가격과 할인가가 동일한 경우도 존재하므로 Hash로 각각 나누려했으나 배열로도 해결될듯하여 간단하게 풀어보았다.

오름차순으로 정렬되어 있고 할인가와 원가격 두개는 짝지어지므로 할인가가 원 가격을 찾으면 visit을 통해 지워주었다.

 

import java.io.*;
import java.util.*;
 
class Solution {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
 
        for (int Tc = 1; Tc <= T; Tc++) {
            StringBuilder sb = new StringBuilder();
            int N = sc.nextInt();
 
            Long[] answer = new Long[N]; 
            long[] num = new long[N * 2]; // 10^9 이므로 Long형 사용.
            boolean[] used = new boolean[N * 2];
 
            for (int i = 0; i < 2 * N; i++) {
                long temp = sc.nextLong();
                num[i] = temp;
                used[i] = true;
            }
             
            int idx = 0; 
            for (int i = 0; i < 2 * N; i++) {
                if (used[i]) {
                    long cur = num[i];
                    for (int j = i; j < 2 * N; j++) {
                        long before = cur * 4 / 3;
                        if (num[j] == before && used[j]) { 
                        // 할인가의 원가격과 동일하고, 사용되지 않았다면
                            answer[idx] =  cur; 
                            used[j] = false;
                            used[i] = false;
                            idx++;
                            break;
                        }
                    }
                }
            }
             
            sb.append("#" + Tc + " ");
            for (Long a : answer) {
                sb.append(a + " ");
            }
            System.out.println(sb);
        }
    }
}
 

 

간단했다