문제 이해
랜덤하게 값들이 입력될 것이다.
이 값들 중 2개를 골라 그 합의 절대값이 최소인 쌍을 고르는 문제이다.
만약 쌍이 여러개일 경우 아무 것이나 출력하면 된다.
문제 풀이
먼저 중요한 점은 1 2를 골라 3이 되더라도 3이 최소값이면 그것이 답이라는 점이다
즉, 양수인지 음수인지는 별 문제가 없다.
또한 답이 오름차순으로 나와야 한다는 것이다.
이 문제는 Array의 한 값을 선택하여, 그 값과 가장 작은 절대값의 합을 가지는 쌍을 구하는 문제이다. 결국 탐색에 관련된 문제이며, "조건을 만족하는 최소값"을 찾는 문제이기 때문에 Parametric Search를 활용하였다.
하지만 이 조건을 찾는 데 시간이 걸렸다.
나는 이 문제에서 두 값을 더했을 때 양수와 음수로 값이 변하는 시점이 가장 중요하다고 생각했다. 만약 index = k일 때 음수가이고 index = k+1일 때가 양수라면, 분명히 0 ~ k-1 index는 합의 절대값 더 작아질 것이고, k+2 ~ N까지는 합의 절대값이 무조건 커질 것이라고 생각했기 때문이다.
따라서, 두 개를 더했을 때 양수가 되는 가장 작은 index를 구하는 것을 목표로 두었다.
또한, index = k인 상황과 index = k+1인 상황의 합의 절대값은 두 개를 직접 비교해보지 않는 이상 알 수가 없었다.
따라서 이 부분에 대한 로직도 넣어줬으며, 조건을 "두 개를 더했을 때 양수가 되는 최소값"으로 두었기 때문에 k+1을 구하는 상황일 것이다. 따라서 Search의 결과값이 T일 때 T-1인 상황도 같이 고려하여 비교해주었다.
- 참고로, 아래 구현에서 보이겠지만 index+1을 통해 우리가 Parametric Search를 통해 도출해 낼 수 있는 최소값은 0 + 1 = 1이라는 것을 알 수 있다. 따라서, if(T==0)인 경우는 고려하지 않아도 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] arr;
static int ans = Integer.MAX_VALUE;
static int ans_pos = 0;
static int ans_neg = 0;
static StringBuilder sb = new StringBuilder();
static Integer pos(int index) {
int value = -arr[index];
int left = index + 1;
// 같은 index끼리는 더하지 못하고, 0 ~ (index-1)까지와 더하는 경우는
// 이전 Binary Search에서 모두 해봤다.
// 따라서 index+1부터 Search를 진행한다.
int right = N-1;
int mid, tmp;
int res = right;
/*
-99 1 2 3의 경우를 생각해보자
-99 + 2, -99+3이 모두 음수이므로 아래에 tmp>=0 분기는 한번도
들어가지 않는다.
이 경우 arr의 끝에 있는 값이 (즉, -99+3이) 그나마 최소값이므로
res = right으로 지정했다.
*/
while(left <= right) {
mid = (left + right) / 2;
tmp = arr[mid] - value;
if(tmp>=0) {
// 조건을 만족 시킬 경우
res = mid;
right = mid - 1;
}else {
left = mid + 1;
}
}
return res;
}
static void min(int pos, int neg) {
if(pos-1!=neg && Math.abs(arr[neg]+arr[pos-1])<ans) {
// 가끔 pos = neg+1인 경우가 존재하여 pos-1 = neg가 될 경우가 존재한다
// 같은 용액끼리는 섞지 못하는 것이 문제 조건이므로 생략해줘야 한다
ans = Math.abs(arr[neg]+arr[pos-1]);
ans_neg = neg;
ans_pos = pos - 1;
}
if(Math.abs(arr[neg]+arr[pos])<ans) {
// pos()의 index + 1 연산에 의거하여 무조건 neg < pos이다.
ans = Math.abs(arr[neg]+arr[pos]);
ans_neg = neg;
ans_pos = pos;
}
}
public static void main(String[] args) {
FastReader sc = new FastReader();
N = sc.nextInt();
arr = new int[N];
for(int i =0;i<N;i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr); // 중요한 부분!!!!
int tmp;
for(int i =0;i<N-1;i++) {
tmp = pos(i);
// tmp : arr[i]와 가장 작은 절대값의 합을 갖는 arr index
min(tmp, i);
}
int ans1 = arr[ans_neg];
int ans2 = arr[ans_pos];
// ans_neg < ans_pos이고 arr는 이미 Sorting되어 있으므로
// 자동으로 오름차순으로 출력 될 것이다.
sb.append(ans1).append(" ").append(ans2);
System.out.println(sb);
}
static class FastReader
// Scanner보다 빠른 입력을 위한 클래스
// 내가 직접 구현한 클래스가 아니기 때문에 생략했다.
}
결과
-
시간 초과 : 지금까지 문제를 풀면서 가장 돌아버릴 것 같았던 문제였다. 투 포인터 방법을 활용하여 풀었다가 시간 초과가 발생하여 Parametric Search로 방향을 돌렸는데 시간 초과가 뜨길래 반나절 정도 고민하다 다른 사람들의 답을 봤다. 하지만 다른 사람도 이와 같은 방식으로 풀었길래 당황스러웠다
결론은 Scanner를 통해 입력을 받았었는데, 입력값을 받는데에 걸린 시간 초과였다. FastReader 클래스를 받아오자마자 시간 초과가 안 되는 것을 보고 조금 멍해졌던 기억이였다. -
4,5번째 줄 틀렸습니다 : pos = neg + 1인 Case를 고려하지 않아 가끔 pos -1 = neg인 Case도 생각하여 틀리게 된 경우였다. 분기 조건을 좀 더 고민하자
-
2,3번째 줄 틀렸습니다 : 처음에 pos()의 res = N으로 두어, 만약 while문이 내가 원하는 조건을 한 번도 안 돌았을 경우 arr[N]을 확인하게 되어 생기는 경우였다. 나중에 min()에 pos!=N이라는 조건을 넣었어서 Index관련 에러는 발생하지 않았지만, 만약 [-11,10]이라는 Case가 존재하여 -11과 10을 봐야하는 경우 pos = N이라서 두 번째 조건문을 확인하지 못하고, neg + 1 = pos라서 첫 번째 조건문을 확인하지 못하는 이상한 경우가 생겼다.
이를 해결하기 위해 res = N-1로 두어 두 번째 조건문은 어떤 경우가 있어도 무조건 수행되도록 만들었다.
