문제
자동차 제조 과정에서는 다양한 테스트를 통해 해당 자동차가 잘 만들어졌는지를 평가합니다.
이러한 평가 지표 중 하나는 자동차의 연비입니다.
자동차의 연비가 높을수록 연료 소비가 적고, 더 많은 거리를 주행할 수 있으므로 이는 자동차가 잘 만들어졌는지의 지표로 사용될 수 있습니다.
만약 3대의 자동차를 테스트하고, 각각의 연비를 측정한다고 가정해봅시다.
첫 번째 자동차의 연비는 9km/L,
두 번째 자동차의 연비는 15km/L,
세 번째 자동차의 연비는 20km/L이라고 합시다.
이 경우, 중앙값은 15km/L이 됩니다.
따라서 이 데이터에서는 중앙값을 이용하여 자동차의 평균적인 연비를 파악할 수 있으며,
이는 자동차 제조 과정에서 테스트의 결과를 평가하는 데 활용될 수 있습니다.
n대의 자동차를 새로 만들었지만 여건상 3대의 자동차에 대해서만 테스트가 가능한 상황입니다.
n대의 자동차의 실제 연비 값이 주어졌을 때, q개의 질의에 대해 임의로 3대의 자동차를 골라 테스트하여 중앙값이 mi값이 나오는 서로 다른 경우의 수를 구하는 프로그램을 작성해보세요.
풀이
- 정렬을 하면 편하겠단 생각이 든다.
- 정렬 후에, q개의 질의에 대해서 각각 왼쪽에서 한대, 오른쪽에서 한대를 선택하면 경우의 수를 구할 수 있다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입력과 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
// 연비를 저장할 배열 입력과 초기화. 아래와 같이 stream을 이용할 경우 for문을 이용할 필요가 없습니다.
int[] efficiency = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 연비를 오름차순으로 정렬합니다.
// 내림차순으로 정렬해도 동일합니다.
Arrays.sort(efficiency);
for (int i = 0; i < q; i++) {
int m = Integer.parseInt(br.readLine());
// 정답의 초기값을 0으로 설정합니다.
int ans = 0;
// Arrays의 이분탐색을 이용할 경우, 찾는 값이 없을 경우 음수값을 반환합니다.
int index = Arrays.binarySearch(efficiency, m);
// 찾는 값이 있는 경우 그 값은 0보다 크거나 같습니다.
// 하지만 찾는 값의 index가 0인 경우 어차피 ans가 0이므로 index >= 0을 index > 0 으로 사용하셔도 괜찮습니다.
if (index >= 0) {
// 풀이에 작성한대로, 찾는 값의 왼쪽에서 1대, 오른쪽에서 1대를 선택하는 경우의 수를 곱한 값을 ans에 저장합니다.
ans = index * (n - index - 1);
}
System.out.println(ans);
}
}
}위의 경우 java의 Arrays에 있는 binarySearch를 이용한 풀이입니다.
import java.io.*;
import java.util.*;
public class Main {
static int[] efficiency;
public static void main(String[] args) throws IOException {
// 입력과 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
// 연비를 저장할 배열 입력과 초기화. 아래와 같이 stream을 이용할 경우 for문을 이용할 필요가 없습니다.
efficiency = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
.toArray();
// 연비를 오름차순으로 정렬합니다.
// 내림차순으로 정렬해도 동일합니다.
Arrays.sort(efficiency);
for (int i = 0; i < q; i++) {
int m = Integer.parseInt(br.readLine());
// 정답의 초기값을 0으로 설정합니다.
int ans = 0;
// binarySearch를 통해 찾는 값이 있는지 확인합니다.
int index = binarySearch(m);
// 찾는 값이 있는 경우 그 값은 0보다 크거나 같습니다.
// 하지만 찾는 값의 index가 0인 경우 어차피 ans가 0이므로 index >= 0을 index > 0 으로 사용하셔도 괜찮습니다.
if (index >= 0) {
// 풀이에 작성한대로, 찾는 값의 왼쪽에서 1대, 오른쪽에서 1대를 선택하는 경우의 수를 곱한 값을 ans에 저장합니다.
ans = index * (n - index - 1);
}
System.out.println(ans);
}
}
private static int binarySearch(int value) {
int left = 0;
int right = efficiency.length - 1;
while (left <= right) {
// 중간값을 구합니다.
// int mid = (left + right) / 2; 로 작성하셔도 됩니다.
// overflow 방지를 위해 아래와 같이 작성합니다.
int mid = left + (right - left) / 2;
// 찾는 값이 있을 경우 해당 index를 반환합니다.
if (efficiency[mid] == value) {
return mid;
} else if (efficiency[mid] < value) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 찾는 값이 없을 경우 음수값을 반환합니다.
return -1;
}
}binarySearch를 직접 구현한 코드입니다.
이분탐색의 경우 정말 자주 사용하므로 코드를 익혀두시면 좋습니다.
