[Java] 백준 3273 두 수의 합

3273 두 수의 합 문제 링크

문제분석

• n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있음
• 1 ≤ ai ≤ 100,000
• 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램

제약 사항

입력 조건

• 첫째 줄 : 수열의 크기 N (1 ≤ N ≤ 100,000)
• 둘째 줄 : 수열
• 셋째 줄 : x (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력 조건

• 조건을 만족하는 쌍의 개수 출력

#1

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

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

        int target = Integer.parseInt(br.readLine());

        int start = 0;
        int end = 1;
        int answer = 0;

        while (start != N) {
            while (end != N) {
                if (arr[start] + arr[end] == target) {
                    answer++;
                    break;
                }
                end++;
            }
            start++;
            end=start+1;
        }
        bw.write(answer+"");

        bw.flush();
        bw.close();
    }
}

#2

• 그냥 냅다 start, end 인덱스를 만든다고 투 포인터 알고리즘을 쓴 게 아님..
• 배열을 조건에 맞춰 정렬해서 start, end를 효율적으로 거쳐야 함

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

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

        int target = Integer.parseInt(br.readLine());

        int start = 0;
        int end = N-1;
        int sum = 0;
        int answer = 0;

        Arrays.sort(arr);

        while (start < end) {
            sum = arr[start] + arr[end];
            if(sum==target) {
                answer++;
                start++;
                end--;
            }
            else if(sum<target) start++;
            else end--;
        }
        bw.write(answer+"");
        bw.flush();
        bw.close();
    }
}

• 성공!