[백준] 3273번 - 두 수의 합

 

3273번: 두 수의 합

 

 

 

 

문제

n개의 정수로 이루어진 수열에서 수열의 요소인 Ai, Aj와 그외 주어지는 자연수 x에 대하여 Ai + Aj = x를 만족하는 (Ai, Aj)의 쌍의 갯수를 구하시오.

 

 

 

조건

수열의 요소를 Ai라고 할때 1 <= Ai <= 1,000,000

두 요소의 합인 x에 대해 1 <= x <= 2,000,000

수열의 크기 n에 대해 1 <= n <= 100,000

 

 

 

 

풀이 방향

두 요소 Ai와 Aj의 합은 다음과 같은 세 가지 경우에 속한다. (Ai < Aj 라고 가정)

i) Ai + Aj < x

ii) Ai + Aj == x

iii) Ai + Aj > x

 

이 문제의 경우 수열의 구성하는 수들 중에서 단 두 개의 수만을 골라 그 합이 x와 같은지 비교해봐야 한다. 따라서 가장 먼저 가장 작은 요소와 가장 큰 요소의 합을 x와 비교하여 위 세 경우 중 어디에 속하는지에 따라 진행을 달리한다. 

 

case i)

현재 Aj는 수열에서 가장 큰 수이기 때문에 Ai는 어떠한 수와도 조건을 만족시키지 못한다. 따라서 i)의 경우에는 Ai 그 다음으로 큰 수와 Aj의 조합을 비교해본다. 

 

case ii) 

Ai + Aj == x라는 조건에 부합하므로 출력할 변수에 1을 더하고 두 번째로 작은 수와 두 번째로 큰 수가 조건에 부합하는지 확인한다.

 

case iii)

현재 Ai 는 가장 작은 수 이기 때문에 Aj는 어떤 수와도 조건을 만족시키지 못한다. 따라서 Ai와 그 다음으로 큰 수에 대해서 판단한다.

 

 

위 과정을 Ai == Aj가 되면 반복을 종료하는데, 조건에 의하면 반드시 수열 내 두 개 요소의 조합만이 답이 될 수 있기 때문이다.

 

또한 위 세 가지 경우는 언제나 현재 가장 작은 요소와 현재 가장 큰 요소간의 합을 비교한다. 따라서 사전에 해당 수열을 정렬시켜두어야 한다.

 

int left = 0; // 가장 작은 요소의 인덱스
int right = arr.length - 1; // 가장 큰 요소의 인덱스
int count = 0; // 출력할 갯수

while (left < right) {

    int sum = arr[left] + arr[right];
	
    // 조건에 부합하는 경우
    if (sum == x) {
        count++;
        left++;
        right--;
    }
    
    //두 수의 합계가 x보다 크다면 현재 가장 큰 수인 arr[right]은 어떠한 경우에도 조건에 부합할 수 없다. 따라서 그 다음으로 큰 수를 비교
    else if (sum > x) 
        right--;
        
    // 두 수의 합계가 x보다 작다면 현재 가장 작은 수인 arr[left]는 어떠한 경우에도 조건에 부합할 수 없다. 따라서 그 다음으로 작은 수를 비교
    else 
        left++;
}

 

 

 

 

 

 

전체 코드

import java.util.*;

public class Main {
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.nextLine());
        int[] arr = new int[n];
        
        String[] input = sc.nextLine().split(" ");
        for (int i=0; i<n; i++) 
            arr[i] = Integer.parseInt(input[i]);
        
        Arrays.sort(arr);
        
        int x = Integer.parseInt(sc.nextLine());
        
        int left = 0;
        int right = arr.length - 1;
        int count = 0;
        while (left < right) {
            
            int sum = arr[left] + arr[right];
            
            if (sum == x) {
                count++;
                left++;
                right--;
            }
            else if (sum > x) 
                right--;
            else 
                left++;
        }
        
        
        System.out.println(count);
        
        sc.close();
    }
}