SW Expert 19113 JAVA : 식료품 가게

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYxCRFA6iiEDFASu

SW Expert Academy

 

 

 

풀이방법 (접근 방법 & 시간복잡도)

가격 배열과 사용했는지 여부를 확인하는 check 배열을 선언한다.

가격배열 뒤에서부터 순회하면서 해당 가격의 3/4 인 가격이 나올때까지 앞으로 가고, 해당 배열에 사용했다는 표시를 해준다.

위와같은 과정을 반복하여 끝까지 순회하다보면 check 배열에는 할인된 가격만 true 표시가 되어있다.

 

시간복잡도 => O(N^2)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= T; t++) {
            int N = Integer.parseInt(br.readLine());
            long[] price = new long[N*2];
            boolean[] check = new boolean[N*2];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 2*N; i++) {
                price[i] = Long.parseLong(st.nextToken());
            }
 
            for (int i = 2*N-1; i >= 0 ; i--) {
                if(!check[i]) { //사용했는지 확인
                    long discount = price[i]*3/4;
                    for (int j = i-1; j >= 0 ; j--) {
                        if(price[j] == discount && !check[j]) {
                            check[j] = true;
                            break;
                        }
                    }
 
                }
            }
 
 
            sb.append("#").append(t).append(" ");
            for (int i = 0; i < 2*N; i++) {
                if(check[i]) {
                    sb.append(price[i]).append(" ");
                }
            }
            sb.append("\n");
 
        }
 
        System.out.println(sb);
    }
}

결과