BOJ2470 두 용액

 

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

시간을 많이 소모하였다. 

1. min값 설정을 잘못하였다. 합의 범위는 곱하기2 +1 을 해주어야 한다.

2. 출력 오름차순을 하지 않앗다.

3.서로 다른 용액을 골라야 한다. -> 이분탐색에서 조건문으로 처리해주어야 한다. 음수일 경우 left를 m+1로 하는 등

import java.util.*;
import java.io.*;
public class Main
{
    
    public static int find(int[] arr, int number){
        int l=0;
        int r=arr.length-1;
        

        
        int min = 2_000_000_001;
        while(l<=r){
            int m = (r+l)/2;
            if(number>=0 && arr[m]==number) {
                r=m-1;
                continue;
            }
            if(number<0 && arr[m]==number) {
                l=m+1;
                continue;
            }
            if(Math.abs(number+arr[m])<Math.abs(min)) min = number+arr[m];
            if(number+arr[m]>0) r=m-1;
            else if(number+arr[m]<0) l=m+1;
            else return 0;
        }
        return min;
        
    }
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(br.readLine());
	    String[] input = br.readLine().split(" ");
	    int[] num = new int[n];
	    for(int i=0;i<n;i++){
	        num[i]= Integer.valueOf(input[i]);
	    }
		
		Arrays.sort(num);
		
		
// 		젤 큰것이음수면 제일 큰거 두개
// 		젤 작은게 양수면 제일 작은거 두개
		if(num[0]>=0){
		    System.out.println(Math.min(num[0],num[1])+" "+Math.max(num[0],num[1]));
		    return;
		}
		if(num[n-1]<=0){
		    System.out.println(Math.min(num[n-1],num[n-2])+" "+Math.max(num[n-1],num[n-2]));
		    return;
		}
		
		
		
		int min_sum= 2_000_000_001;
		int min_value1= 1_000_000_001;
		int min_value2= 1_000_000_001;
 		for(int i=0; i<n; i++){
 		    int foundSum = find(num,num[i]);
 		    if(Math.abs(foundSum)<Math.abs(min_sum)){
 		        min_sum=foundSum;
 		        min_value1 = num[i];
 		        min_value2 = foundSum-num[i];
 		    }
		}
		
		System.out.println(Math.min(min_value1,min_value2)+" "+Math.max(min_value1,min_value2));
		
		
		
	}
}

 

import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static int findNearestValue(int[] arr, int leftIndex, int rightIndex, int findValue) {
        int nearestValue = arr[leftIndex];
        int nearestDiff = Math.abs(findValue - nearestValue);
        int l = leftIndex + 1, r = rightIndex;
        while (l <= r) {
            int m = (l + r) / 2;
            int diff = Math.abs(findValue - arr[m]);
            if (diff < nearestDiff) {
                nearestValue = arr[m];
                nearestDiff = diff;
            }
            if (arr[m] < findValue) l = m + 1;
            else if (arr[m] > findValue) r = m - 1;
            else return findValue;
        }
        return nearestValue;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = sc.nextInt();

        Arrays.sort(arr);

        int ansAbs = Math.abs(arr[0] + arr[1]);
        int ans1 = arr[0];
        int ans2 = arr[1];
        for (int i = 0; i < N - 1; i++) {
            int pairValue = findNearestValue(arr, i + 1, N - 1, -arr[i]);
            int sumAbs = Math.abs(arr[i] + pairValue);
            if (ansAbs > sumAbs) {
                ansAbs = sumAbs;
                ans1 = arr[i];
                ans2 = pairValue;
            }
        }
        System.out.println(ans1 + " " + ans2);
    }
}

 

 

Set 메소드 활용

 

Set의 floor, ceiling 메소드는 해당값에서 가장 가까운 값을 반환한다. floor의 경우 가장 가까운 작은 수, ceiling은 큰 수

import java.util.Scanner;
import java.util.TreeSet;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int ansAbs = 2000000001;
        int ans1 = 0;
        int ans2 = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            Integer[] pairValues = {set.floor(-x), set.ceiling(-x)};
            for (Integer pairValue : pairValues) {
                if (pairValue == null) continue;
                int sumAbs = Math.abs(x + pairValue);
                if (ansAbs > sumAbs) {
                    ansAbs = sumAbs;
                    ans1 = x;
                    ans2 = pairValue;
                }
            }
            set.add(x);
        }
        System.out.println(Math.min(ans1, ans2) + " " + Math.max(ans1, ans2));
    }
}