[백준 / Java] 2473번: 세 용액 (골드3)

문제 풀이 날짜: 2023.10.13
포스트 작성일: 2023.10.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2473번: 세 용액 (골드3)

 

키워드

이분 탐색

 

풀이 접근법

• 주어진 수의 범위가 크므로 범위에 주의하자. 배열이나 변수를 Long으로 선언해야 한다.
• 세 가지 용액을 혼합하여 답을 도출해야 하므로, 서로 다른 세 용액을 가리키는 변수(ansL, ansR, ansM)를 선언하였다.
• 하나의 mid를 기준점으로 잡고, 양 끝에서부터 left와 right를 좁혀가며 이분탐색을 한다. 이분 탐색 포인터가 범위를 넘어갔다면 mid의 위치를 조정하여 다시 양 끝부터 탐색한다.
• 현재까지 발견한 0에 가장 가까운 특성값 key를 갱신하며 탐색을 진행한다. key보다 더 작은 특성값이 발견된다면 key를 더 작은 값으로 갱신하고 그 순간의 left, right, mid를 저장한다.
  • 용액의 특성값이 0보다 작다면, 0에 더욱 가까운 근사치를 찾기 위해 특성값이 조금 더 큰 용액을 더해보아야 한다. 따라서 left를 1 증가시킨다.
  • 반대로 용액의 특성값이 0보다 크다면 특성값이 조금 더 작은 용액을 더해보아야 한다. 따라서 right를 1 감소시킨다.
• mid가 배열 끝 인덱스까지 커졌다면 탐색을 종료한다. 이 때 ansL, ansR, ansM에 저장된 값들이 0에 가장 가까운 특성값을 만드는 세 용액을 가리키는 포인터 변수이다.

 

코드

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 void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		long[] sol = new long[N];

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

		Arrays.sort(sol);

		int ansL = 0;
		int ansR = 0;
		int ansM = 0;
		
		long key = Long.MAX_VALUE;

		for(int mid = 1; mid < N - 1; mid++) {
			int left = 0;
			int right = N - 1;
			while (left <= right) {
				long mixed = sol[left] + sol[right] + sol[mid];
				
				if(left >= mid || right <= mid) { break; }
				
				if(Math.abs(0 - mixed) < Math.abs(0 - key)) {
					key = Math.abs(0 - mixed);
					ansL = left;
					ansR = right;
					ansM = mid;
				}
				
				if (mixed < 0) {
					left++;
				} else if (mixed > 0) {
					right--;
				} else { //(mixed == 0) : 최적해를 찾았다면
					break;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(sol[ansL]).append(" ").append(sol[ansM])
			.append(" ").append(sol[ansR]);
		
		System.out.print(sb);
	} 

}

---

 

 

git 링크

(git 링크 첨부)