[백준/Java] 2470 두 용액

조건

1. 산성 용액의 특성값은 양수 1에서 부터 1,000,000,000 알칼리성 용액의 특성값은 -1 부터 -1,000,000,000 이다. 그렇기에 int를 사용해도 문제가 없다.

2. 전체의 용액의 수 인 N이 입력되고 특성 값들이 입력된다.

3. 특성값들은 산성 알칼리성 순서상관없이 입력된다.

예제

해결

여기서 사용될 방법은 정렬 및 이진탐색이다. 일단 A 배열을 정렬을 하여 오름차순으로 정렬을 한다. 그 후 맨 왼쪽의 인덱스부터 시작에 Value들을 덧셈을 하여 0에 더 가까워지는 값들을 찾는다.

전체 코드

import java.io.BufferedReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.InputStreamReader;
import java.io.FileReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;

public class Main {
	
	static int N;
	static int[] A;
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();
	
	static void input() {
		N = scan.nextInt();
		A = new int[N+1]; // 배열의 index를 1부터 시작하기 N +1 를 해준다.
		for(int i =1 ; i<=N; i++) {
			A[i] = scan.nextInt(); // 값들을 배열에 담아준다.
		}
	}
	
    
	static int findAns(int[] A, int L, int R, int X) {
		int result = R +1 ; 
		
		while(L <= R) { // L 값이 R값보다 같아지거나 커지기 까지 반복한다.
            int mid = (L + R) /2; // mid값을 넣어주고 
			if(A[mid] >= X) {  // A[mid] 값이 x 보다 크거나 같으면 result에 
				result = mid ; // mid값을 넣고 R에 mid -1 을 해준다.
				R = mid - 1; (여기서 왜 >= 이냐면 해당 값보다 같아야지 0이 됨
			} else { 		// 그렇지 않다면 L에 mid + 1 을 해준다.
			
				L = mid + 1;
		    }
        }
		return result;
	}
	
	
	
	static void find() {
		Arrays.sort(A, 1, N + 1); // A 배열을 오름차순으로 정렬해준다.
        
		int v1= 0 , v2 =0;
		int sum = Integer.MAX_VALUE; 
		for(int i = 1; i <= N - 1; i++) { // 맨 왼쪽 값 부터 그 다음 값들을 										 // 덧셈하여 0에 가까운 값을 												// return한다 
        
			int result = findAns(A,i+1,N,-A[i]); // 
			
            // 혹시나 return을 받은 값의 하나 앞이 더 작을 수 있기 때문에 if문
            // 으로 result보다 1 작은 값으로 비교하여 sum 값보다 작다면 sum에			 // 다가 해당 값을 넣어준다.
			if(i < result - 1 && Math.abs(A[i] + A[result -1] ) < sum) {
				sum = Math.abs(A[i] + A[result - 1]);
				v1 = A[i];
				v2 = A[result - 1];
			}
			// 수정중
			if(result <= N&& Math.abs(A[i] + A[result] ) < sum) {
				sum = Math.abs(A[result] + A[i]);
				v1 = A[i];
				v2 = A[result];
			}
		}
		
		sb.append(v1).append(' ').append(v2);
		System.out.println(sb);
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
    input();
    find();
	}
	
	static class FastReader {
	BufferedReader br;
	StringTokenizer st;
	
	public FastReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
		}
	
	public FastReader(String s) throws FileNotFoundException {
		br = new BufferedReader(new FileReader(new File(s)));
		}
	
	
	String next() {
		while(st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch(IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
		}
	
	int nextInt() {
		return Integer.parseInt(next());
	}
	long nextLong() {
		return Long.parseLong(next());
	}
	
	double nextDouble() {
		return Double.parseDouble(next());
	}
	
	String nextLine() {
		String str= "";
		try {
			str = br.readLine();
		} catch(IOException e) {
			e.printStackTrace();
		}
		return str;
		}
	}

}