[백준] 보물 (BufferedReader, greedy 그리디 알고리즘, StringTokenizer, Arrays.sort(), 내림차순, 1026번, Java)

ㅂ

 

문제설명

입력 & 출력

 

나의 풀이

 

이번 문제는 길이가 N인 두 배열을 계산하는 점화식 A [N-1] × B [N-1]이 최솟값을 가지게 만드는 문제입니다.

 

위 점화식 그대로 사용하게 된다면 1*2 + 1*7 + 1*8 + 6*3 + 0*1 ➡️ 35가 나오게 됩니다.

 

이때 배열의 정렬을 하고 작은 값과 큰값을 서로 곱해주면 최솟값이 나옵니다.

 

먼저 빠른 입력을 위해 BufferedReader 클래스를 사용하여 입력을 받아주고 StringTokenizer 클래스를 사용하여 공백을 기준으로 분리를 해서 배열에 저장을 합니다.

 

그리고 Arrays.sort() 메서드를 사용하여 A를 오름차순으로 정렬해 주고, B배열을 내림차순으로 정렬합니다. (A와 B의 정렬이 바뀌어도 상관없습니다.)

 

이 때 오름차순은 상관없지만 내림차순을 할경우에 Warapper 클래스를 사용해야 합니다.

 

따라서 B배열을 초기화하는 21번째 줄을 보면 Int가 아닌 Integer로 선언했습니다. 그리고 Collections의 reverseOrder()메서드를 사용하여 내림차순으로 정렬해줍니다.

 

그리고 정렬된 각 배열을 각각 곱해준 값을 누적하여 반환하면 됩니다.

 

문제에서 B배열은 재배열 하지말라고 했는데
B 배열을 Arrays.sort(B,Collections.reverseOrder()); 와 같이 정렬하는 것은 문제의 조건을 위반하지 않습니다.
정렬은 각 요소의 크기 순서를 바꾸는 것이지 배열의 순서를 바꾸는 것은 아니기 때문입니다.

 

 

 

참고❗️

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기