백준 2470 두 용액 (JAVA 자바 풀이: 이분 탐색 활용)

백준 2470 두 용액 (JAVA 자바 풀이)

 

---

 

 

 

---

 

처음 풀이한 방식은 다음과 같다. 

 

1) 숫자 배열을 정렬한 후  -> O(nlogn)

2) 모든 숫자를 돌면서 -> O(n) 

3) 해당하는 숫자의 역부호(마이너스면 플러스, 플러스면 마이너스)를 취한 값을 바이너리 서치로 찾되 -> O(logn)

4) 정확히 일치하는 숫자가 없으면 근사값을 리턴하여 

5) 최소값을 갱신하면서 가장 0과 가까운 쌍을 찾는다 -> O(1) 

 

시간 복잡도에서는 문제가 없었지만 로직이 잘못되어 다음과 같은 반례를 만날 경우 잘못된 답을 리턴했다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int N = Integer.parseInt(stringTokenizer.nextToken());
      int[] numbers = new int[N];
      stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      while (N-- > 0) {
         numbers[N] = Integer.parseInt(stringTokenizer.nextToken());
      }

      Arrays.sort(numbers);
      int smallest = Integer.MAX_VALUE;
      int a = 0;
      int b = 0;
      for (int i = 0; i < numbers.length; i++) {
         int number = numbers[i];
         int find = binarySearch(reverseSign(number), numbers);
         if (Math.abs(number + find) < smallest){
            smallest = Math.abs(number + find);
            a = Math.min(number, find);
            b = Math.max(number, find);
         }
      }
      System.out.println(a + " " + b);
   }

   private static int reverseSign(int number) {
      return -number;
   }

   private static int binarySearch(int number, int[] numbers) {
      int left = 0;
      int right = numbers.length -1;
      int mid = 0;
      while (left <= right) {
         mid = (left + right) / 2;
         if (numbers[mid] == number) {
            if (isSelf(number, numbers[mid])){
               return Math.min(Math.abs(number - numbers[mid+1]), Math.abs(number - numbers[mid-1]));
            }
            return numbers[mid];
         } else if (numbers[mid] > number) {
            right = mid -1;
         } else {
            left = mid + 1;
         }
      }

      if (isSelf(number, numbers[mid])){
         return Math.min(Math.abs(number - numbers[mid+1]), Math.abs(number - numbers[mid-1]));
      }

      return numbers[mid];
   }

   /**
    * 자기 자신인 경우를 판별해주어야 한다.
    */
   private static boolean isSelf(int number, int numbers) {
      return numbers - number == 0;
   }
}

 

input :
5
-98 -97 1 2 92
    
output :
-97 92
    
correct ans :
1 2

 

 

 

접근 로직 자체는 맞았지만 세부 코드 구현에서 수정이 필요했다. 

 

 

1) 각 값에 대해 자기 자신을 제외하고 탐색하는 부분 

int left = 1 + index; // 자기 자신을 제외하고 시작한다.

left 값을 1로 주고 인덱스를 더해주면 이미 배열이 정렬된 상태이기 때문에 자기 자신을 제외하고 탐색할 수 있다. 

 

 

2) 각 값에 대한 절대값 합의 최소값을  binary search로 찾는 부분 

 

이전 코드에서는 반대 부호와 mid 넘버를 비교하여 찾기만 하였지만, 바뀐 코드에서는 반대 부호를 사용하지 않고 각각의 숫자 자신에 대해서 값을 찾도록 하였다. 어차피 로직은 같지만 꼬아서 생각할 필요가 없어서 좀 더 개선되었다. 

 

또 하나는 binarySearch 메서드 자체에서 최소값을 찾으면서도 각각의 sum과 절대값 sum을 구해서 비교한다는 것이다. 이전코드에서는 단순히 근사치를 arr[mid]로 리턴하도록 했는데, 개선된 코드에서는 sum을 전부 직접 찾고 비교하기 때문에 정확도 면에서 확실한 최소값임을 보장받을 수 있다. 

 

 

 

3) 틀리기 쉬운 부분인데 초기값을 0이 아니라 실제 배열의 값으로 해준다 

 

입력이 2개로 

2
1 2

위와 같이 주어진다면 초기값을 0으로 했을 때 0을 리턴한다. 

 

 

 

 

 

💡 코드 구현

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {

		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		int N = Integer.parseInt(stringTokenizer.nextToken());
		int[] numbers = new int[N];
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		while (N-- > 0) {
			numbers[N] = Integer.parseInt(stringTokenizer.nextToken());
		}

		Arrays.sort(numbers);
		int smallest = Integer.MAX_VALUE;
		int a = numbers[0];
		int b = numbers[1];
		for (int i = 0; i < numbers.length; i++) {
			int number = numbers[i];
			int find = binarySearch(i, numbers);
			if (Math.abs(number + find) < smallest){
				smallest = Math.abs(number + find);
				a = Math.min(number, find);
				b = Math.max(number, find);
			}
		}
		System.out.println(a + " " + b);
	}

	private static int binarySearch(int index, int[] numbers) {
		int current = numbers[index];
		int find = numbers[0];
		int sumAbsSmallest = Integer.MAX_VALUE;
		int left = 1 + index; // 자기 자신을 제외하고 시작한다.
		int right = numbers.length -1;
		int mid = 0;
		while (left <= right) {
			mid = (left + right) /2;

			int sum = current + numbers[mid];
			int sumAbs = Math.abs(sum);

			if (sumAbs< sumAbsSmallest){
				sumAbsSmallest = sumAbs;
				find = numbers[mid];
			}

			if (sum==0){
				return numbers[mid];
			}
			if (sum <0 ){
				left = mid+1;
			} else{
				right= mid-1;
			}
		}
		return find;
	}


}