알고리즘/그리디

[백준] 1018번: 보물 자바(Java)

park-walnut 2024. 12. 28. 17:28

문제

접근법

곱셈은 곱해지는 두 수가 클수록 결괏값이 커지기 때문에 둘 중 하나의 값이 작아지면 결과가 확연히 작아진다.

기본접근 ⇒ A를 정렬하고 B를 역정렬하여 같은 위치의 수를 곱해주고 그 결과의 합을 구한다.

 

하지만 이 문제는 단순정렬로도 해결할 수 있지만 그리디 알고리즘을 활용하면 더욱 효과적으로 해결이 가능하다.

Queue구조의 pop을 활용한다고 생각하면 코드의 이해가 더 빠를 것이다. A에서 최소를 갖는 값의 인덱스와 B에서 최대를 갖는 값의 인덱스를 찾아 해당하는 인덱스를 리스트에서 pop 시키고 계산하는 것을 N번 반복하는 것이다.

 

풀이

첫번째 풀이: 단순 정렬

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
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 s_A = new StringTokenizer(br.readLine());
        StringTokenizer s_B = new StringTokenizer(br.readLine());
        ArrayList<Integer> A = new ArrayList<>(N);
        ArrayList<Integer> B = new ArrayList<>(N);

        for (int i = 0; i < N; i++) {
            A.add(Integer.parseInt(s_A.nextToken()));
            B.add(Integer.parseInt(s_B.nextToken()));
        }

        Collections.sort(A);//정렬
        Collections.sort(B, Collections.reverseOrder());//역정렬

        int sum = 0;
        for (int i = 0; i < N; i++) {
            Integer a = A.get(i);
            Integer b = B.get(i);
            sum += a*b;
        }

        System.out.println(sum);
    }
}

 

두 번째 풀이: Queue 구조 활용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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 s_A = new StringTokenizer(br.readLine());
        StringTokenizer s_B = new StringTokenizer(br.readLine());
        ArrayList<Integer> A = new ArrayList<>(N);
        ArrayList<Integer> B = new ArrayList<>(N);

        for (int i = 0; i < N; i++) {
            A.add(Integer.parseInt(s_A.nextToken()));
            B.add(Integer.parseInt(s_B.nextToken()));
        }

        int sum = 0;

        for (int i = 0; i < N; i++) {
            int minA = Collections.min(A);
            int maxB = Collections.max(B);

            sum += minA * maxB;

            A.remove(Integer.valueOf(minA));
            B.remove(Integer.valueOf(maxB));
        }

        System.out.println(sum);
    }
}

 

사실 두 방법의 성능 자체는 비슷하다. 하지만 그리디 알고리즘에 대해서 더욱 깊게 공부하기 위해 두 방법 모두 시도해 보는 것을 추천한다.

 

트러블슈팅

이슈 1

  • 문제
    • 숫자만 입력받는데 Scanner가 아닌 BufferedReader를 쓰는게 맞을까?
  • 원인
    • Scanner vs BufferedReader 차이점
      1. 입력 처리 방식
        • Scanner: 입력값을 토큰(단어, 숫자 등) 단위로 처리 (nextInt(), nextLine() 등)
        • BufferedReader: 입력값을 문자열로 읽어 들이고 수동으로 파싱해야 함 (readLine() 사용)
      2. 성능
        • Scanner: 내부적으로 입력값을 파싱하므로 속도가 느림
        • BufferedReader: 버퍼를 사용하여 입력 속도가 빠름
      3. 스레드 안전성
        • Scanner: 스레드 안전하지 않음
        • BufferedReader: 동기화를 지원하여 스레드 안전성을 제공함
      4. 사용 편의성
        • Scanner: 사용이 간단하고 직관적
        • BufferedReader: 다소 복잡하며 추가 작업(예: 파싱)이 필요함
      5. 주요 용도
        • Scanner: 간단한 사용자 입력 처리
        • BufferedReader: 대량의 데이터 처리, 파일 입력 등 성능이 중요한 작업
      6. 예외 처리
        • Scanner: 입력값이 예상치 못한 형식일 경우 InputMismatchException 발생
        • BufferedReader: 예외 처리를 개발자가 직접 구현해야 함 (IOException 발생 가능)
  • 해결
    • 그렇다면 Scanner와 BufferedReader 중 어떤 것을 사용해야 할까?
      • Scanner를 사용해야 하는 경우
        • 간단한 프로그램에서 사용자 입력을 처리할 때
        • 입력 데이터의 크기가 작고 간단한 파싱이 필요한 경우
        • 예를 들어, 문제에서 몇 가지 숫자만 입력받아 처리하는 경우
      • BufferedReader를 사용해야 하는 경우
        • 입력 데이터가 대량으로 주어지는 경우
        • 입력 속도가 중요한 상황 (예: 알고리즘 대회, 제한 시간이 중요한 문제 등)
  • 레퍼런스