[백준 알고리즘 자바]2470 : 두 용액

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

2470번: 두 용액

---

문제

• KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 
• 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.
• 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
• 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다.
• 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
• 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는
• 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다.
• 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
• 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

• 첫째 줄에는 전체 용액의 수 N이 입력된다.
• N은 2 이상 100,000 이하이다.
• 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.
• 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다.
• N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

• 첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다.
• 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다.
• 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

입출력 예제

 

---

풀이 방식을 정리해보자

 

1. 버퍼를 사용해서 작성하였고 N, arr[ ], result[ ], lt, rt, min 를 각각 선언하고 초기화한다.

• N : 전체 용액의 수
• arr[ ] : 용액의 특성값을 나타내는 정수들
• result[ ] :  0에 가장 가까운 용액을 만들어내는 두 용액의 특성값
• lt : 맨 왼쪽부터 시작하는 포인터
• rt : 가장 끝인 오른쪽부터 시작하는 포인터
• min : 0과 가장 가까운 값을 찾기 위한 변수

2. 먼저 Arrays.sort() 를 사용해서 배열을 오름차순으로 재정렬한다.

• Arrays.sort() : 배열을 자동으로 오름차순으로 정렬해준다.

3. lt가 rt보다 작을 때에 반복해서 수행하는 while문을 작성한다. 

 

4. sum 변수를 선언하고, arr[lt] + arr[rt] 값을 넣는다.

• 0과의 차이를 알기 위해서 arr[lt]와 arr[rt] 값을 더해서 sum에 저장한다.

5.  Math.abs() 를 사용해서 min 값이 Math.abs(sum) 값보다 크면 min에 sum의 절댓값을 넣는다.

• Math.abs() : 절댓값을 리턴한다.
• sum에 저장된 값을 절댓값으로 리턴하면, 0과의 차이값을 알 수 있다.

6. result[0]에는 arr[lt], result[1] 에는 arr[rt] 값을 넣어준다.

• arr[lt] : 0에 가까운 용액을 만드는 두 용액 중, 왼쪽에 위치한 용액
• arr[rt] : 0에 가까운 용액을 만드는 두 용액 중, 오른쪽에 위치한 용액  

7. sum 이 0 일때에 break 를 걸어준다.

• 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 하나를 출력해야하기 떄문이다.

8. sum에 저장된 값이 0보다 작다면(음수) lt를 더해주고, 그게 아니라면(양수) rt를 더해준다.

 

9. result[ ] 배열에 저장된 2개의 원소를 출력한다.

 

수행 결과를 확인한다.

답안 소스

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 IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] result = new int[2];
		int lt = 0;
		int rt = N-1;
		int min = Integer.MAX_VALUE;
		
		Arrays.sort(arr);
		
		while(lt < rt) {
			int sum = arr[lt] + arr[rt];
			
			if(min > Math.abs(sum)) {
				min = Math.abs(sum);
				
				result[0] = arr[lt];
				result[1] = arr[rt];
				
				if(sum == 0) break;
			}
            
			if(sum < 0) lt++;
			else rt--;
		}
		System.out.println(result[0] + " " + result[1]);
	}
}

---

혼자 작성해본 소스는 틀렸다고 나왔다. 임의로 다른 예시를 넣었을 때에 값이 이상하게 나왔으니 확실하다.

다만 왜 틀린건지를 모르겠어서 일단 올려본다. 혹시라도 답변을 받을 수 있을까 싶어서..

틀린 답안 소스

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

public class Main {
	public ArrayList<Integer> solution(int N, int[] arr) {
		ArrayList<Integer> result = new ArrayList<>();
		int sum = 0;
		int min = Integer.MAX_VALUE;
		int lt = 0;
		int rt = N-1;
		
		Arrays.sort(arr);
		
		while(lt < rt) {
			sum = arr[lt] + arr[rt];

			if(Math.abs(sum) < min) {
				min = Math.abs(sum);
				
				result.add(arr[lt]);
				result.add(arr[rt]);
			}
			
			if(sum < 0) lt++;
			else rt--;
			
		}		
		return result;
	}
	
	public static void main(String[] args) {
		Main sol = new Main();
		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();
		}
		System.out.println(sol.solution(N, arr));
	}
}