[백준] 3273 두 수의 합 (JAVA)

문제 링크:

3273번: 두 수의 합

 

 

난이도: 실버 3

 

 

문제:

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

 

 

입력:

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

 

 

출력:

문제의 조건을 만족하는 쌍의 개수를 출력한다.

 

 

문제 이해:

문제 이해는 쉽다. N개의 서로다른 숫자인 수열이 주어졌을때,

 

두개의 숫자를 더하여 입력한 X를 만드는 쌍이 몇개인지 구하는 것이다.

 

예제 입력 1을 예시로 들어보면

9
5 12 7 10 9 1 2 3 11
13

13 을 만드는 쌍 개수는

(12, 1) (10, 3) (2, 11)로 총 3개이다.

 

 

구현 방향:

작성자는 처음에 바깥 while로 index를 0..N-2까지 돌리고, 매번 안쪽 for가 index+1..N-1까지 훑었다.
매칭이 빨리 발견되면 break로 빨리 끝내서 구현하여 정답이 나왔다. 이는 O(N^2)이다.

 

하지만 정답률이 낮았기에 다른 사람들에 구현을 보고 투포인터 방식이 사용되는 것을 확인 하였다.

작성자는 운이 좋게 시간초과를 피한 것이다.

 

즉 주어진 수열을 정렬 후

• L은 가장 작은 값(0) 부터,
• R은 가장 큰 값(N-1) 부터 시작.

이 두 수의 합(arr[L] + arr[R])이

• x보다 작으면 → 합을 키워야 하므로 왼쪽 포인터를 오른쪽으로 이동 (L++)
• x보다 크면 → 합을 줄여야 하므로 오른쪽 포인터를 왼쪽으로 이동 (R--)
• x와 같으면 → 조건 만족 → 카운트하고 양쪽 포인터 모두 이동 (L++, R--)

즉 투포인터 방식을 사용하면  스킵을 많이하여 O(N log N)로 해결할 수 있다.

 

정답 코드는 다음과 같다.

 

 

정답 코드:

O(N^2) 정답 코드:

public class Main {
    static int N;
    static int[] arr;
    static int result = 0;
    static int x;

    public static void solve() {
        int index = 0;
        while (index != N - 1) {
            for (int i = index + 1; i < N; i++) {
                if (arr[index] + arr[i] == x) {
                    result++;
                    break;
                }
            }
            index++;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        x = Integer.parseInt(br.readLine());

        solve();
        System.out.println(result);
    }
}

 

 

O(NlogN) 정답 코드:

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

public class Main {
    static int N;
    static int []arr;
    static int result=0;
    static int x;

    public static void solve(){
        int L=0;
        int R=N-1;
        while (R>L){
            //투포인터 합이 정답인 경우
            if(arr[L]+ arr[R]== x) {
                result ++;
                L++;
                R--;
            }
            // 투포인터 합이 x보다 작으면 더이상 탐색 불필요
            else if(arr[L]+ arr[R]<x) L++;

            //투포인터 합이 x보다 크면 탐색 수행
            else  R--;
        }

    }
    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());

        arr=new int[N];

        StringTokenizer st=new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }

        x=Integer.parseInt(br.readLine());

        Arrays.sort(arr);
        //초기 세팅 끝

        //탐색 시작
        solve();

        //결과 출력
        System.out.println(result);

    }
}

 

 

감사합니다.