BOJ - 2467 용액

2467 용액 : https://www.acmicpc.net/problem/2467

---

Problem

---

Solve

서로 다른 두 용액의 합이 0과 가장 가까운 것을 찾는 문제.

이분 탐색을 이용해서 start = 첫번째 용액, end = 마지막 용액으로 초기화 한 후 arr[start]+arr[end]가 양수이면 두 합의 크기를 줄이면서 양수의 범위를 줄이기 위해 end--, 음수이면 두 합의 크기를 줄이면서 음수의 범위를 줄이기 위해 start++를 함으로써 탐색범위를 줄이고 두 용액의 합을 절대값으로 변환하여 0과 가장 가까운 수의 두 용액의 값과 두용액의 합을 갱신하는 것을 반복한다.

---

Code

public class 용액 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[] sequence = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<N;i++){
			sequence[i] = Integer.parseInt(st.nextToken());
		}

		int start=0;
		int end=N-1;
		int firstResult = 0;
		int lastResult = 0;
		StringBuilder sb = new StringBuilder();
		int min = Integer.MAX_VALUE;
		while(start<end){
        	//서로 다른 두용액의 합
			int sum = sequence[start]+sequence[end];
            //합의 절대값
			int target = Math.abs(sum);

			//0에 더 가까운 두 용액 합의 절대값으로 갱신
			if(target<min){
				firstResult = sequence[start];
				lastResult = sequence[end];
				min = target;
			}

			//두 용액의 합이 양수이면 양수쪽의 범위를 줄여준다.
            //음수라면 음수쪽의 범위를 줄여준다.
            //0이라면 0인 아무값을 반환해도 된다는 조건이 있기때문에 그냥 break
			if(sum>0){
				end--;
			}else if(sum<0){
				start++;
			}else{
				break;
			}
		}

		sb.append(firstResult);
		sb.append(" ");
		sb.append(lastResult);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference