[백준_9024번] 두 수의 합

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

9024번: 두 수의 합

[문제]

 여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 구하시오. 예를 들어, 10 개의 정수

 

S = { -7, 9, 2, -4, 12, 1, 5, -3, -2, 0}

 

가 주어졌을 때, K = 8 에 그 합이 가장 가까운 두 정수는 {12, -4} 이다. 또한 K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의 다섯 종류가 있다.

여러 개의 서로 다른 정수가 주어졌을 때, 주어진 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수에 가장 가까운 두 정수의 조합의 수를 계산하는 프로그램을 작성하시오.

 

[입력 조건]

 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄에 한 개의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 n 과 K (2 ≤ n ≤ 1,000,000, -108 ≤ K ≤ 108 )가 한 개의 공백을 사이에 두고 입력된다. 두 번째 줄에는 n 개의 정수가 하나의 공백을 사이에 두고 주어지며, 각 정수의 최댓값은 108 이고, 최솟값은 -108 이다. 잘못된 데이터가 입력되는 경우는 없다.

 

[코드]

import java.io.*;
import java.util.*;

public class BaekJoon_9024 {
	static int n,k,min;
	static int[] num;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int t=Integer.parseInt(br.readLine());
		
		while(t-->0) {
			st=new StringTokenizer(br.readLine());
			
			n=Integer.parseInt(st.nextToken());
			k=Integer.parseInt(st.nextToken());
			min=Integer.MAX_VALUE;
			num=new int[n];
			
			st=new StringTokenizer(br.readLine());
			for(int i=0;i<n;i++) 
				num[i]=Integer.parseInt(st.nextToken());
			
			Arrays.sort(num);
			
			System.out.println(Two_Pointer());
		}
	}
	
	static int Two_Pointer() {
		int left=0;
		int right=n-1;
		
		int count=0;
		while(left<right) {
			int sum=num[left]+num[right]; // 두 수의 합
			
			if(sum>=k) // 합이 k보다 크다면 큰 수 빼기 -> right--
				right--;
			
			else // 합이 k보다 작으면 더 큰 수 더하기 -> left++
				left++;
			
			/*
			 * min은 k와 k와 가까운 수의 차가 저장된 변수
			 * min이 갱신될 때 마다 k와 가까운 수의 개수를 구하는 count 초기화 
			 */
			if(Math.abs(k-sum)<min) {
				min=Math.abs(k-sum);
				count=1;
			}
			// k와 가까운 정수를 발견하면 count 증가
			else if(Math.abs(k-sum)==min)
				count++;
		}
		
		return count;
	}
}

 

[고찰]

 이번 문제는 투포인터를 사용하는 문제였다. 수열 저장한 배열을 오름차순으로 정렬한 후 배열의 맨 처음을 가리키는 left와 맨 끝을 가리키는 right의 합을 구해 k 값과 비교해야 한다. 이때 주의할 점은 두 수의 합이 k인 경우를 구하는 것이 아니라 k와 가까운 값이 나오는 경우의 수를 구하는 것이다. 

 따라서 k와 두 수를 더한 값을 뺀 값을 min에 저장하고 더 작은 min 값을 찾을 때 마다 여태까지 k 값과 가까운 값을 count 한 변수를 초기화 해주어야 한다.이 점만 주의한다면 쉽게 해결할 수 있는 문제였다.