문제 탐색하기
입력값 관리하기
- T는 테스트 케이스의 개수, n과 m은 각각의 배열의 크기다
- 이어서 오는 값들은 각각 n크기의 배열과 m 크기의 배열의 원소다.
- 이 입력을 앞서 받은 T의 크기만큼 반복한다
목표 정리
- 두 배열이 주어졌고 n의 배열의 원소와 m 배열의 원소들과 비교했을 때,
그 절댓값 차이가 가장 작은 값을 구해야한다 - 이어서 그 값들을 모두 더해서 출력해야 한다
해결방법 추론
- 가장 쉬운 방법은 2중 포문으로 브루트포스 하는 방법이다
- 하지만 최대 입력값을 보자마자 이 방법으로는 시간초과가 발생할 것이라고 예측할 수 있다
- 그럼 다른 방법이 없을까 생각해봤을 때, 범위를 좁혀서 탐색하는 이분탐색을 생각할 수 있다
- m배열의 인덱스의 범위를 이분탐색의 범위로 잡고
그 안의 원소 중에 해당하는 값이 있다면 찾아서 더해주면된다 - 만약 범위를 벗어났거나 정확한 값이 m 배열에 없는 경우,
이분탐색으로 좁힌 범위 중에서 가장 왼쪽 인덱스의 값과 오른쪽 인덱스의 값의,
해당 원소와의 절댓값 차이를 비교하여 더 작은 쪽을 더해주면된다 - 그리고 배열의 원소의 값은 최대 10^9이 될 수 있으므로 정답을 합하는 변수의 타입은
int형 타입이 아닌 long형 타입으로 선언하여 출력해야함도 잊지 말아야한다!
시간복잡도 계산
- 이분탐색의 시간복잡도는 log(m)만큼 발생한다
- 이때 n만큼 순회하면서 m의 크기를 갖는 배열을 이분탐색하므로 n x log(m)의 연산이 발생한다
- 이어서 테스트케이스만큼 반복하니 최종 시간복잡도는 O(T x (n x log(m)))이 발생한다
- 대략 10^7 * 6...정도 발생하니 시간제한인 2초안에는 해당 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리하기
- 테스트케이스와 각 크기는 변수로 관리하며, n과 m크기의 배열을 각각 만들어 입력값들을 관리해준다
전체 탐색 설계
- 이분탐색을 위해 먼저 m의 크기를 갖는 배열을 오름차순 정렬을 해준다
- 이어서 n만큼 순회하면서 이분탐색을 진행한다.
- 이분탐색을 위해 left와 right를 각각 0과 m-1로 설정하며,
중간에 정확한 원소를 찾을 수도 있으니 isFind라는 체크 변수도 하나 선안한다 - 이분탐색을 진행하고, 만약 정확한 원소를 발견하지 못했다면
현재원소와 left, right인덱스의 원소와의 절댓값 차이를 비교한다 - 둘중 차이가 더 작은쪽을 정답 변수에 더해주며,
같을때는 둘중 아무나 더해도 상관없기 때문에 여기서 작은쪽을 더해주는 것을 선택했다
이분탐색 설계
- 위 과정사이에 있는 이분탐색을 설계하자
- 이 이분탐색은 인덱스 범위를 대상 범위로 하기 때문에 다른 이분탐색과는 조금 다르다
- 중간값은 동일하게 구하며,
현재 n 크기의 배열의 값과 mid 위치의 값과 같다면 발견 체크하고 정답 변수에 더해주고 탈출한다 - 만약 n 크기의 배열의 값이 더 크다면 left에 mid를 넣어주고 작다면 right에 mid를 넣어준다
- 여차 다른 경우와 다르게 mid-1, mid+1을 하지 않는 이유는 인덱스의 범위를 탐색하기 때문이다
- 이후 발견하지 못한경우 left와 right를 재활용하기 때문에
인덱스 범위 예외를 피하기 위해 위와같이 설정하였다 - 따라서 탐색 조건도 left+1이 right보다 작은 경우로 설정하였다
출력 설계
- long타입의 ans를 전체 탐색 전에 선언해둔다
- 탐색을 통해 완성한 ans를 테스트케이스마다 출력해주면 정답이 된다
정답 코드
(1회차 시도 성공!)
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));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr1 = new int[n];
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr1[j] = Integer.parseInt(st.nextToken());
}
int[] arr2 = new int[m];
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
arr2[j] = Integer.parseInt(st.nextToken());
}
long ans = 0;
Arrays.sort(arr2);
for (int j = 0; j < n; j++) {
int left = 0;
int right = m-1;
boolean isFind = false;
while(left+1 < right){
int mid = (left + right) / 2;
if(arr1[j] == arr2[mid]){
isFind = true;
ans += arr1[j];
break;
}else if(arr1[j] > arr2[mid]){
left = mid;
}else if(arr1[j] < arr2[mid]){
right = mid;
}
}
if(!isFind){
if(Math.abs(arr1[j] - arr2[left]) <= Math.abs(arr1[j] - arr2[right])){
ans += arr2[left];
}else if(Math.abs(arr1[j] - arr2[left]) > Math.abs(arr1[j] - arr2[right])){
ans += arr2[right];
}
}
}
bw.write(ans+"\n");
}
br.close();
bw.close();
}
}
문제 링크
Software Developer