[백준] 2470 : 두 용액

더해서 0에 가장 가까운 용액을 구하는 것이니 기준이 되는 값에 -1을 곱하여 그와 가장 가까운 수 이분탐색으로 구함.

 

투포인터로 더 빠르고 쉽게 구현할 수 있는 것 같았는데 이분탐색 공부 중이여서 이분탐색으로 해결함.

나중에 투포인터 공부할 때가 되면 한 번 더 해봐야겠다.

 

메모리 : 28328 KB

시간 : 408 ms

코드길이 : 2367 B

 

[내 코드]

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

public class Main {
	public static int[] arr;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int n = 0; n < N; n++) {
			arr[n] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr); //이진탐색위해 오름차순 배열
		
		int[] result = new int[2];//최소가 되는 쌍을 닮을 배열
		Arrays.fill(result, 1000000000); //결과값 출력을 위한 배열
		
		if(N == 2) {
			result[0] = arr[0];
			result[1] = arr[1];
		}
		
		else {
			for(int n = 0; n < N; n++) {
				int makeNear0 = binarySearch(arr[n], 0, N - 1);
				if(Math.abs(arr[n] + makeNear0) < Math.abs(result[0] + result[1])) {
						result[0] = arr[n];
						result[1] = makeNear0;
				}
			}
		}
		if(result[0] < result[1])
			sb.append(result[0]).append(" ").append(result[1]);
		else if(result[1] < result[0])
			sb.append(result[1]).append(" ").append(result[0]);
		
		System.out.print(sb);

	}
	
	static int binarySearch(int num, int low, int high) {
		int mid;
		int reverseNum = num*-1; //num과 더했을 때 0인 수
		int min = 2000000000; //가장 작은 차이를 가진 수를 찾기 위해 변수 선언 
		int smallest = 0;
		while(low <= high){
			mid = (low + high) / 2;
			if(reverseNum == arr[mid]) {
				if(arr[mid] != num)
					return arr[mid]; //더했을 때 0이면 바로 리턴
				else
					return smallest;
			}
			else if(reverseNum < arr[mid]) {
				if(arr[mid] != num) {//비교대상인 자기자신이 나오면 그냥 넘어가기
					if(arr[mid] - reverseNum < min) {
						min = arr[mid] - reverseNum; //수와의 차이가 가장 작은 차이보다 작으면 교체
						smallest = arr[mid];// 비교대상과 더했을 때 최소가되는 값 저장
					}
				}
				high = mid - 1;
			}
			else if(reverseNum > arr[mid]) {
				if(arr[mid] != num) {
					if(reverseNum - arr[mid] < min) {
						min = reverseNum - arr[mid];
						smallest = arr[mid];
					}
				}
				low = mid + 1;
			}
		}
		return smallest;
	}

}

1등 코드

메모리 : 12504 KB

시간 : 128 ms

코드길이 : 1252 B

 

[1등 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        int n = readInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++)
            arr[i] = readInt();
        Arrays.sort(arr);
        int[] solution = new int[2];
        int idx1=0, idx2 = n-1;
        int min = Integer.MAX_VALUE;
        int sum,abs;
        while(idx1<idx2){
            sum = arr[idx1]+arr[idx2];
            abs = Math.abs(sum);
            if(abs<min){
                min = abs;
                solution[0] = arr[idx1];
                solution[1] = arr[idx2];
            }
            if(sum==0) break;
            else if(sum<0) idx1++;
            else idx2--;
        }
        System.out.println(solution[0]+" "+solution[1]);
    }


    //////////////////////////////////////////////////
    static int readInt() throws IOException {
        int n = 0;
        boolean isNegative = false;
        while (true) {
            int input = System.in.read();
            if (input<=32)
                return isNegative ? n * -1 : n;
            else if(input=='-')
                isNegative = true;
            else
                n = (n<<3) + (n<<1) + (input&15);
        }
    }
}