백준 1026번 : 보물 (JAVA)

https://www.acmicpc.net/problem/1026

1026번: 보물

지문에 A 배열은 정렬이 가능하지만, B배열은 정렬하지 말라는 조건이 있지만,

풀고나서 다른 사람들 풀이를 참고하니 다들 B배열까지 정렬하길래 풀이를 남겨본다.

풀이 방법

풀이방법으로는 A배열을 오름차순으로 정렬한 뒤,

A배열의 가장 작은 값과 B배열의 가장 큰 값을 순서대로 찾도록 했다.(A배열의 가장 작은 값과 B배열의 가장 큰 값이 곱해지도록) 그리고 B배열에 같은 값이 중복해서 들어가 있을 수 있기 때문에 visitedB라는 배열을 만들어서 B배열 인덱스에 방문을 체크하도록 했다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N+1];
        int[] B = new int[N+1];
        boolean[] visitedB = new boolean[N+1]; //같은 인덱스 방문을 피하기 위한 체크용 배열

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=1; i<=N; i++) {
            A[i] = Integer.parseInt(st.nextToken()); 
        }
        st = new StringTokenizer(br.readLine()," ");
        for(int i=1; i<=N; i++) {
            B[i] = Integer.parseInt(st.nextToken()); 
        }
        //end input
        Arrays.sort(A); //A배열을 오름차순으로 정렬한다
        int sum = 0;

        for(int i=1; i<=N; i++) { //A배열 순회
            int maxIndex = 0;//B배열에 가장 큰 값이 들어있는 인덱스 저장

            for(int j=1; j<=N; j++) { //B배열 순회
                if(B[j]>=B[maxIndex] && visitedB[j]==false) { //maxIndex에 저장된 값보다 더 큰 값고 처음 방문이라면
                    maxIndex = j; //maxIndex를 현재 index로 바꿔줌
                }
            }//B배열 순회 끝
            visitedB[maxIndex] = true;
            sum += A[i]*B[maxIndex];
        }//A배열 순회 끝
        System.out.println(sum);


    }//end main
}

시간 복잡도가 올라가긴 했지만, B배열을 정렬하지 않고 풀 수 있다.