[백준] 1026 - 보물 - JAVA[자바] (feat. B 재배열 X, B sort X)

 

[접근 방법]

"B에 있는 수 를 재배열하면 안 된다" 라는 말에 꽂혀 여러 방법으로 풀어보게 되었다.

 

B에 있는 수를 재배열하면 안된다는 말은

1. 단순히 "Sort하면 안된다."
-> B의 배열을 손상시키면 안된다.

Arrays.sort(B)를 하면
B는 sort 된 상태로 남아있게 되므로 B에 있는 수를 재배열하는 것이다
가장 나쁜 풀이라고 평가 하고 싶다.
개인적 평가: 1.0 / 5.0
근데, 구글에 검색해보니 해당 방법을 10중 8, 9 분이 사용하고 계신것 같다. 왤까..

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int[] arrA = new int[N];
        int[] arrB = new int[N];
        int sum = 0;
        
        // 배열 A 생성
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
        	arrA[i] = Integer.parseInt(st.nextToken());
        }
        
        // 배열 B 생성
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
        	arrB[i] = Integer.parseInt(st.nextToken());
        }
        
        // 정렬
        Arrays.sort(arrA);
        Arrays.sort(arrB);
        
        // A의 가장 작은 수와 B의 가장 큰 수 곱해주기 
        for(int i = 0; i < N; i++) {
        	sum += arrA[i] * arrB[N-1-i];
        }
        
        System.out.println(sum);   
    }
}

 

 

 

2. B만 직접적으로 건들지 않으면 된다.
이 부류의 그나마 괜찮았던 풀이법은
풀이법: 그럼 원래 B는 냅두고 가짜 B를 받아와서 정렬하면 되겠다! ( 꼼수 ) 였다.
그래도 B를 직접 sort하지 않으니까. 그래도 이건 말장난 아니야..?

개인적 평가 2.0 / 5.0

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int[] arrA = new int[N];
        int[] arrB = new int[N];
        int sum = 0;
        
        
        for(int i = 0; i < N; i++) {
        	arrA[i] = Integer.parseInt(st.nextToken());
        }
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
        	arrB[i] = Integer.parseInt(st.nextToken());
        }
       
        int[] fakeB = arrB;
        
        Arrays.sort(arrA);
        Arrays.sort(fakeB);
        
        for(int i = 0; i < N; i++) {
        	sum += arrA[i] * fakeB[N-1-i];
        }
        
        System.out.println(sum);
        
    }
    
}

 

3. N 이 50 이내이므로 탐색하면서 B의 가장 큰 값과 A의 가장 작은 값들을 곱해주면 되겠다.

Array 는 값을 삭제하면서 Array를 줄여나갈 수 없다.
1) Array에서 해당 값을 빼면서 유효한 값이 아닌 -1로 변하게 하고, 해당 값을 지나치기
-> O(N^2)

2)ArrayList를 사용해 값을 삭제하면서 시행한다.
-> O(N^2)... 해보고서야 자각했다. N -> N-1 -> N-2 -> ........-> 2 -> 1이라고 그래도 좀 더 줄겠지 하고 ArrayList를 사용하려 생각했는데 멍청했다.

개인적 평가 4.5 / 5.0

ArrayList를 사용했다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.ArrayList;


public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int[] arrA = new int[N];
        ArrayList<Integer> arrB = new ArrayList<>();
        int sum = 0;
        
        
        for(int i = 0; i < N; i++) {
        	arrA[i] = Integer.parseInt(st.nextToken());
        }
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            arrB.add(Integer.parseInt(st.nextToken()));
        }
        
        Arrays.sort(arrA);
        

		// B의 size가 0이 될 때까지 반복
        while(arrB.size() > 0){

            for(int j = 0; j < N; j++) {

                int max = Integer.MIN_VALUE;
                // 삭제할 인덱스 저장할 변수
                int index_to_delete = 0;

                for(int i = 0; i < arrB.size(); i++) {
                    int temp = arrB.get(i);

                    if (temp > max){
                        max = temp;
                        index_to_delete = i;
                    }
                }
                arrB.remove(index_to_delete);

        	    sum += arrA[j] * max;
            }
        
        }
        
        System.out.println(sum);
    }
    
}

 

 

표본이 워낙 작아 자료구조의 차이에서 생기는 크게 유효한 시간차이는 없는 것 같다.

 

그래도 문제의 조건을 지키고 싶었다.

 

나중에 "다루는 문제의 조건이 더욱 까다로워질 때 막히지 않을" 경험을 계속 쌓아나가고 있다.