📖 [백준알고리즘 풀이] Q.3273 두 수의 합 풀이 - java

📖 문제

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

n개의 서로 다른 양의 정수 a1, a2, …, an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다.

자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

🔍 접근법

Q.3273 두 수의 합 문제입니다.

n개의 서로 다른 양의 정수들로 이뤄진 수열이 있을 때

ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 문제입니다.

오직 두개의 수만을 골라 x값과 같은 경우가 몇개인 지를 구하는 문제입니다.

투 포인터 방식으로 풀이가 가능합니다.

우선 수열을 정렬을 해주고

시작점 = 0, 끝점 = n - 1 부터 각각 시작해 시작점과 끝점이 같아지기 전까지!

시작점과 끝점의 원소를 더합니다.

해당 합이 x와 같다면 count를 늘려주고 start 를 늘려주고 end는 줄여줍니다.

주어진 n개의 정수가 모두 서로 다른 양의 정수이므로

각 수마다 한개의 쌍을 가질 수 밖에 없기 때문입니다.

ex) 1,2,3,4,5 가 주어지고 x=5 일 때
1의 짝은 오직 4만 가능  1+4 = 5
2의 짝은 오직 3만 가능  2+3 = 5

해당 합이 x보다 작다면 더 큰 수를 더해봐야하기 때문에 start 지점을 1 늘려주고

반대로 합이 x보다 크다면 합을 줄여줘야 하기 때문에 end 지점을 1 줄여줍니다.

start와 end가 같아지기 전까지 이를 반복하면 답을 도출할 수 있습니다.

while (start < end){
            int sum = sequence[start]+sequence[end];
            if(sum == x){       // sum이 x와 같은 경우
                start ++;
                end --;
                count++;
            }
            else if(sum < x ){  // sum이 x보다 작은 경우
                start++;
            }  
            else{               //sum이 x보다 큰 경우
                end--;
            }
}

💻 코드

package problem.twopointer;

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

public class Main_3273 {
    static int n,x;
    static int sequence[];
    static int count = 0;


    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(count);
    }

    public static void solve(){
        int start = 0;
        int end = n-1;
        Arrays.sort(sequence);
        while (start < end){
            int sum = sequence[start]+sequence[end];
            if(sum == x){
                start ++;
                end --;
                count++;
            }
            else if(sum < x ){
                start++;
            }
            else{
                end--;
            }
        }
    }


    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        sequence = new int[n];
        String temp[] = br.readLine().split( " ");
        for(int i=0; i<n; i++){
            sequence[i] = Integer.parseInt(temp[i]);
        }
        x = Integer.parseInt(br.readLine());
        br.close();
    }

}

Written on March 17, 2021