3273번: 두 수의 합

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

문제

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)

출력

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

예제 입력 1

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1

3

+) 예제 입력 2

4
1 2 3 4
4

+) 예제 출력 2

1

풀이

• 이분 탐색

  • 부등호 실수 주의

    

package binary_search;

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

public class Main_3273 {

    private static int lengthOfSequence;
    private static int[] sequence;
    private static int numberToMake;
    private static int result;

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        sequence = new int[lengthOfSequence];

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

        numberToMake = Integer.parseInt(br.readLine());
    }

    private static void process() {
        Arrays.sort(sequence);

        for (int i = 0; i < lengthOfSequence; i++) {
            int leftOperand = sequence[i];
            int rightOperand = numberToMake - leftOperand;

            if (leftOperand < rightOperand) {
                binarySearch(0, lengthOfSequence - 1, rightOperand);
            }
        }
    }

    private static void binarySearch(int start, int end, int targetNumber) {
        int mid = (start + end) / 2;
        int currentNumber = sequence[mid];

        if (start > end) {
            return;
        }

        if (currentNumber == targetNumber) {
            result++;
            return;
        }

        if (currentNumber < targetNumber) {
            start = mid + 1;
        }

        if (currentNumber > targetNumber) {
            end = mid - 1;
        }

        binarySearch(start, end, targetNumber);
    }

    private static void output() {
        System.out.println(result);
    }

}

• 투 포인터

  • left → 맨 왼쪽

  • right → 맨 오른쪽

    package two_pointer;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.util.StringTokenizer;
    
    public class Main_3273 {
    
        private static int lengthOfSequence;
        private static int[] sequence;
        private static int numberToMake;
        private static int result;
    
        public static void main(String[] args) throws IOException {
            input();
            process();
            output();
        }
    
        private static void input() throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st;
    
            lengthOfSequence = Integer.parseInt(br.readLine());
    
            sequence = new int[lengthOfSequence];
    
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < lengthOfSequence; i++) {
                sequence[i] = Integer.parseInt(st.nextToken());
            }
    
            numberToMake = Integer.parseInt(br.readLine());
        }
    
        private static void process() {
            int left = 0;
            int right = lengthOfSequence - 1;
    
            Arrays.sort(sequence);
    
            while (left < right) {
                if (sequence[left] + sequence[right] == numberToMake) {
                    result++;
                }
    
                if (sequence[left] + sequence[right] < numberToMake) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    
        private static void output() {
            System.out.println(result);
        }
    }