문제
해결 방안 고민
S = A[0] * B[0] + ... + A[N - 1] * B[N - 1]
- S의 값을 가장 작게 만들기 위해 A의 수를 재배열
- 단, B에 있는 수는 재배열하면 안 됨
- S의 최솟값을 출력하는 프로그램
- 큰 수 * 작은 수
A: 1 1 1 6 0 (재배열 O)
B: 2 7 8 3 1 (재배열 X)
=> 1 * 2 + 1 * 7 + 0 * 8 + 1 * 6 + 1 * 3
=> 2 + 7 + 6 + 3 = 18
B의 maxIdx, minIdx 를 찾아서 A의 재배열한 minIdx, maxIdx와 일치시켜줘야 함
Markdown
복사
•
문제를 처음보고 알았다. 최솟값을 구해야 하는데 배열이 두 개인 경우라면 큰 수와 작은 수를 곱했을 때 최솟값이 나올 것이라는 생각이 딱 들었다.
•
문제에서는 A의 수를 재배열하고 B에 있는 수는 재배열하면 안 된다고 하였다.
해결 방법
•
리스트를 활용하여 최댓값, 최솟값을 비교하는 로직을 구현한다.
•
A의 수가 담긴 리스트만 정렬한다.
•
최댓값, 최솟값을 찾으면 해당 인덱스의 값을 기존 리스트에서 제거한다.
•
제거한 리스트의 길이를 고려하여 반복문을 구성한다.
코드
package algo250223;
import java.io.*;
import java.util.*;
// 보물 - 실버 4
public class Baek1026 {
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());
int aN = N;
int bN = N;
// 각각의 리스트 선언
List<Integer> aList = new ArrayList<>();
List<Integer> bList = new ArrayList<>();
// A 리스트 입력
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
aList.add(Integer.parseInt(st.nextToken()));
}
// A 리스트 재배열
Collections.sort(aList);
// B 리스트 입력
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
bList.add(Integer.parseInt(st.nextToken()));
}
int max = Integer.MIN_VALUE; // 최댓값 선언 및 초기화
int min = Integer.MAX_VALUE; // 최솟값 선언 및 초기화
int sum = 0; // 결과값 선언 및 초기화
int aIdx = 0;
int bIdx = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < aN; j++) {
if (min > aList.get(j)) {
aIdx = j;
min = aList.get(aIdx);
}
}
min = aList.remove(aIdx); // 리스트에서 최솟값 제거
for (int k = 0; k < bN; k++) {
if (max < bList.get(k)) {
bIdx = k;
max = bList.get(bIdx);
}
}
max = bList.remove(bIdx); // 리스트에서 최댓값 제거
sum += min * max;
min = Integer.MAX_VALUE; // 최솟값 초기화
max = Integer.MIN_VALUE; // 최댓값 초기화
aN--; // A 리스트 길이를 고려하여 aN 감소
bN--; // B 리스트 길이를 고려하여 bN 감소
}
bw.write(String.valueOf(sum));
bw.flush();
bw.close();
br.close();
}
}
Java
복사
다른 풀이의 코드
•
이 풀이 같은 경우 A와 B를 모두 재배열 하였는데 시간은 내 코드에 비해 다소 빨리 나오기는 했지만 조건을 충족하지 않았다. 다만 이 코드 역시 큰 수와 작은 수를 곱하면 최솟값을 구할 수 있는 아이디어에 착안하여 코드를 작성하였다.
package algo250223;
import java.io.*;
import java.util.*;
// 보물 - 실버 4, 다른풀이
public class Baek1026_2 {
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());
int[] A = new int[N];
int[] B = new int[N];
StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st1.nextToken());
B[i] = Integer.parseInt(st2.nextToken());
}
Arrays.sort(A);
Arrays.sort(B);
int result = 0;
for (int i = 0; i < N; i++) {
result += A[i] * B[N - 1 - i];
}
bw.write(String.valueOf(result));
bw.flush();
bw.close();
br.close();
}
}
Java
복사