[백준 1026]- 보물 - JAVA [배열 B 정렬 X]

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 

백준 1026 보물 포스팅입니다.

 

1026번: 보물

다른 포스팅을 보니깐 B정렬을 다 건드렸더라구요

그래서 여기 코드는 B배열을 정렬하지 않고 푸는 방법입니다.

 

B배열을 건드리면

A배열 오름차순

B배열 내림차순으로

정렬하고 곱하면 정답이 나옵니다.

 

문제를 보면 B배열을 건들지 말라고 하니깐

건들지 않고 풀어보겠습니다.

 

 

일단 지금 보여주는 소스는 틀린 소스입니다.

테스트 케이스는 맞는데 자꾸 틀리더라구요...

뭐 그래서 제 블로그니깐 올립니다~ 이 코드 잘못된 점을 아시는 분은 알려주세요

이 방법은 A배열을 B배열과 맞게 순서를 바꿔주는 코드에요

최솟값을 구해야하니깐 B의 가장큰수랑 A의 가장작은 수랑 배열 순서를 맞추도록 만든 소스인데 틀렸다고 뜨네여..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;

public class Main{
    public static int[] getIdxArr(int n, String a[], String cloneB[]){
        int[] idxArr = new int[n];
        for(int i=0; i < n; i++){
            int max = Integer.parseInt(cloneB[i]);
            for(int j=i; j < n; j++){
                if(max < Integer.parseInt(cloneB[j])){
                    max = Integer.parseInt(cloneB[j]);
                }
            }
            int tmpIdx = Arrays.asList(cloneB).indexOf(String.valueOf(max));
            idxArr[tmpIdx] = i;
            String tmpVal = cloneB[i];
            cloneB[tmpIdx] = tmpVal;
        }
        return idxArr;
    };

    public static int[] getSortA(int n,int idxArr[], String a[]){
        int[] sortA = new int[n];
        int[] intA = new int[n];

        for(int i=0; i< n; i++){
            intA[i] = Integer.parseInt(a[i]);
        }
        Arrays.sort(intA);
        for(int i=0; i< idxArr.length; i++){
            sortA[i] = intA[idxArr[i]];
        }
        return sortA;
    }

    public static int getValue(int n ,int[] sortA , String[] b){
        int sum = 0;
        for(int i=0; i<n; i++){
            sum += (sortA[i] * Integer.parseInt(b[i]));
        }
        return sum;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String[] a = br.readLine().split(" ");
        String[] b = br.readLine().split(" ");
        String[] cloneB = b.clone();
        // b배열내 크기의 값을 구하는 코드
        int[] idxArr = getIdxArr(n, a, cloneB;
        int[] sortA = getSortA(n, idxArr , a);
        int answer = getValue(n, sortA, b);


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

이번 코드가 정답입니다.

이 코드가 휠씬 간단하고 이해하기도 편하실 거에요

/*
 백준 1026 보물
 JAVA
*/

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

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[] a = new int[n];
        ArrayList<Integer> b = new ArrayList<>();
        StringTokenizer stA = new StringTokenizer(br.readLine());
        StringTokenizer stB = new StringTokenizer(br.readLine());

        for(int i=0; i<n; i++){
            a[i] = Integer.parseInt(stA.nextToken());
            b.add(Integer.parseInt(stB.nextToken()));
        }

        Arrays.sort(a);
        int answer = 0;


        for(int i=0; i<n; i++){
            int max = Collections.max(b);
            answer += (max * a[i]);
            b.remove(Integer.valueOf(max));
        }

        System.out.println(answer);
    }
}

 

혹시라도 잘 모르실 분들을 이해 설명을 드리자면

먼저 a배열을 받고 B배열은 ArrayList에 넣어줍니다.

 

여기 중요한 점은 A배열을 오름차순으로 정렬해줘야합니다.

for(int i=0; i<n; i++){
    int max = Collections.max(b);
    answer += (max * a[i]);
    b.remove(Integer.valueOf(max));
}

ArrayList를 사용한 이유는 Collections.max를 사용해서 B배열에 가장 큰 값을 뽑기 위해서입니다.

B배열의 가장 큰 값을 빼고 그 값과 오름차순으로 정렬된 A배열을 순서대로 곱해줍니다.

곱한 후 곱한 가장 큰 값을 ArrayList에서 제거해줍니다.

 

그렇게 반복해주면 최솟값이 나옵니다.

 

궁금하신 점은 댓글에 달아주세요

 

감사합니다~