[ 알고리즘 ] 코딩 - 백준 2473 - 세용액.java

---

문제 링크

www.acmicpc.net/problem/2473

2473번: 세 용액

---

문제개요

BOJ 2473 - (자바) 세용액 - 투포인터

---

두용액이 세개로 늘어난 확장판

so-cute-danu-dev.tistory.com/78

[ 알고리즘 ] 코딩 - 백준 2470 - 두 용액.java

---

입력값 : 알칼리 = -1,000,000,000, 산성 = 1,000,000,000

두 용액의 합이 0에 가까운 것을 찾아내는 문제

모든 입력이 알칼리일 수도 있고, 산성일 수도 있다.

N : 3이상 5000 이하

 

입력예시

출력 예시

---

 

로직

Step 01. 모든 용액의 값을 배열에 입력 받는다

Step 02. 배열을 오름차순 정렬한다

Step 03. 가장 왼쪽부터 가장 오른쪽까지 전체 순회(반복문 인덱스 i)를 하면서 합을 구한다.

Step 03. 가장 왼쪽 인덱스 left하나, 가장 오른쪽 인덱스 right하나를 둔다

Step 04. i번째와 left, right의 인덱스의 원소를 더하고(sum), 그 값의 절대값을 취한다(cur_diff).

Step 05. 절대값을 비교하고 차이가 더 작은 경우 저장한다

Step 06. sum 값이 0보다 크다면 right를 1 줄이고 0보다 작다면 left를 1 늘린다

Step 07. 모든 값을 탐색하고 마지막에 저장되어있는 i번재 인덱스와 left, right 인덱스의 원소가 정답

 

백주 2470번 두 용액에서 조금 더 비튼 문제라 풀이가 비슷하다!

---

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		long[] solutions = new long[N];
		
		StringTokenizer stt = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < N; i++) {
			int next = Integer.parseInt(stt.nextToken());
			solutions[i] = next;
		}
		
		Arrays.sort(solutions);
		
		long[] res = new long[3];
		
		long diff = Long.MAX_VALUE;

		// 가장 왼쪽부터 시작해서 가장 오른쪽 끝까지
		for(int i = 0; i < N; i++) {
			int left = i+1; // 가장 왼쪽을 제외하고 그 다음부터 순회
			int right = N-1;
			
			while(left < right) {
				// 세 용액의 합 계산
				long sum = solutions[i] + solutions[left] + solutions[right];
				
				// 차이 계산
				long cur_diff = Math.abs(sum);
				
				// 차이가 더 작다면 원소 저장
				if(cur_diff < diff) {
					diff = cur_diff;
					res[0] = solutions[i];
					res[1] = solutions[left];
					res[2] = solutions[right];
				}
				
				if(sum > 0) { // 차이가 0보다 크다. 오른쪽 원소를 한 칸 앞으로
					right--;
				} else { // 차이가 0보다 작다. 왼쪽 원소를 한 칸 앞으로
					left++;
				}
			}
		}
		System.out.println(res[0] + " " + res[1] + " " + res[2]);
	}
}