silver 4. 보물 (1026)

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

문제

길이가 N인 정수 배열 A와 B가 있을 때, 함수 S를 아래와 같이 정의할 때 S의 최솟값을 출력하는 프로그램 작성

• S의 값을 가장 작게 만들기 위해 A의 수를 재배열. 단, B에 있는 수는 재배열하면 안됨

입력: 첫째 줄에 N이 주어지고, 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어짐

• N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수

출력: S의 최솟값 출력

풀이

• 아이디어: A, B를 오름차순으로 정렬한 후 A의 가장 작은 수는 B의 가장 큰 수와 곱해주는 방식으로 해결

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();	// 배열 크기 저장
        int[] A = new int[N];
        int[] B = new int[N];
        int result = 0;			// S의 최솟값 저장
        String space = sc.nextLine();	// N의 값을 입력받고 문자를 입력받기 전 기존의 enter 값을 없애주는 변수

        StringTokenizer st = new StringTokenizer(sc.nextLine());  // A의 값을 받아옴
        for(int i=0; i < N; i++){
          A[i] = Integer.parseInt(st.nextToken());  // 받아온 값을 int형으로 변환 후 A에 값을 저장
        }

        StringTokenizer st2 = new StringTokenizer(sc.nextLine());  // B의 값을 받아옴
        for(int i=0; i < N; i++){
          B[i] = Integer.parseInt(st2.nextToken());	// 받아온 값을 int형으로 변환 후 B에 값을 저장
        }

        Arrays.sort(A);		// A를 오름차순으로 정렬
        Arrays.sort(B);		// B를 오름차순으로 정렬
        
        for (int i = 0; i < N; i++){
          result += A[i] * B[N-1-i];	// S의 최솟값을 구함
        }

        System.out.println(result);
    }
}

• 백준에 제출했을 때 코드는 통과했지만, 문제에서 B에 있는 수는 재배열하면 안 된다는 조건을 만족시키지 못했다.
• B에 있는 수를 재배열하지 않으면서 S의 최솟값을 찾을 수 있는 방법을 다시 생각해봐야겠다.

배운점

• nextInt() 메서드 다음 nextLine() 메서드를 실행하면, nextLine() 메서드가 그냥 넘어가버리는 오류가 발생

  • 이유: nextInt() 메서드를 실행할 때 숫자를 입력하고 엔터를 누르면 숫자는 리턴시키지만 엔터의 값은 그대로 남아있음. nextLine() 메서드는 enter 값을 기준으로 메서드를 종료시키기 때문에 nextLine() 메서드가 실행될 때 남아있는 enter 값을 그대로 읽어 바로 종료됨

• 해결 방법: 정수를 입력하고 그 다음 문자를 입력하고자 할 때는 next() 메서드를 사용하거나, 문자를 입력받기 전 nextLine() 메서드를 한번 더 써줘서 기존은 enter 값을 없애주어야 함

추가

• 2022-02-03 추가

  • 처음 풀었을 때는 B에 있는 수를 재배열하지 말라는 조건을 충족시키지 못했다. 조건을 충족시켜 푼 풀이를 추가한다.
  • 아이디어
    • B에서 최댓값을 찾아주는 max 메서드를 생성함
    • A 메서드는 Arrays.sort()를 이용해 오름차순으로 정렬해줌
    • for문을 돌면서 B의 최댓값을 찾아주는 함수를 호출해 B의 최댓값과 A의 최솟값을 곱한 후 result 값에 더해줌

  import java.util.*;
    
  public class Main{
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
    
      int N = sc.nextInt();
      int[] A = new int[N];
      int[] B = new int[N];
      int result = 0;
      String space = sc.nextLine();
    
      StringTokenizer st1 = new StringTokenizer(sc.nextLine());
      for(int i=0; i < N; i++){
        A[i] = Integer.parseInt(st1.nextToken());
      }
    
      StringTokenizer st2 = new StringTokenizer(sc.nextLine());
      for (int i=0; i < N; i++){
        B[i] = Integer.parseInt(st2.nextToken());
      }
    
  	// A를 오름차순으로 정렬
      Arrays.sort(A);
    	
      // B와 같은 값을 가지는 BCopy 생성
      int[] BCopy = Arrays.copyOf(B, N);
    
      for(int i=0; i < N; i++) {
        int B_max = max(BCopy);	// B에서의 최댓값을 찾아줌
        result += A[i] * B_max;	// A의 최솟값과 B의 최댓값을 곱한 후 result에 더해줌
      }
    
      System.out.println(result);
    }
      
    // B에서의 최댓값을 찾아주는 함수
    public static int max(int[] arr){
      int index = -1;	// 최댓값의 인덱스 값을 저장
      int max = -1;	// 최댓값 저장
    
      // for문을 통해 최댓값을 찾아줌
      for(int i=0; i < arr.length; i++){
        if (max < arr[i]){
          max = arr[i];
          index = i;
        }
      }
        
      // 최댓값 다음으로 큰 값을 찾기 위해 최댓값을 가진 인덱스에 해당하는 값을 0으로 변경
      arr[index] = 0;
    
      // 최댓값 return
      return max;
    }
  }
  

• 2022-02-04 추가

  • 스터디 진행하며 코드 리뷰를 하던 중, A의 최솟값과 B의 최댓값을 곱해나가는 과정이 아니라 A의 최댓값과 B의 최솟값을 곱해나가는 과정으로 계산을 하면 통과할까? 라는 질문이 나와 코드를 약간 수정해 테스트해봄
  • 위의 로직으로도 테스트 통과함

  import java.util.*;
    
  public class Main{
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
    
      int N = sc.nextInt();
      int[] A = new int[N];
      int[] B = new int[N];
      int resultMin = 0;
      String space = sc.nextLine();
    
      StringTokenizer st1 = new StringTokenizer(sc.nextLine());
      for(int i=0; i < N; i++){
        A[i] = Integer.parseInt(st1.nextToken());
      }
    
      StringTokenizer st2 = new StringTokenizer(sc.nextLine());
      for (int i=0; i < N; i++){
        B[i] = Integer.parseInt(st2.nextToken());
      }
    
      Arrays.sort(A);
    
      int[] BCopy = Arrays.copyOf(B, N);
    
      for(int i=0; i < N; i++) {
        int B_min = min(BCopy);			// B의 최솟값을 찾아주는 함수 호출
        resultMin += A[N-1-i] * B_min;	// A의 최댓값과 B의 최솟값을 곱해줌
      }
    
      System.out.println(resultMin);
    }
    
    // B의 최댓값을 구해주는 함수 대신 B의 최솟값을 구해주는 함수로 수정
    public static int min(int[] arr){
      int index = 0;
      int min = 101;
    
      for(int i=0; i < arr.length; i++){
        if (min > arr[i]){
          min = arr[i];
          index = i;
        }
      }
    
      arr[index] = 101;
    
      return min;
    }
  }