[백준] 3273. 두 수의 합 - JAVA

문제

 

풀이 과정

서로 다른 양의 정수로 이루어진 수열이 주어질 때 a(i) + a(j) = x를 만족하는 [a(i), a(j)] 쌍의 수를 구하는 문제이다.

 

이중 반복문으로 구현하면 시간 초과가 발생한다.

제한시간은 1초인데 n이 최대 100,000이므로 100,000² => 시간 초과

 

문제 접근

투포인터를 이용해서 반복 횟수를 줄여서 연산 횟수를 줄인다.

 

1. 배열을 오름차순 정렬한다.
2. 투포인터: start를 배열의 첫번째 인덱스, end를 마지막 인덱스로 초기화 한다.
3. 정렬된 형태를 가지므로 단조성을 가진다.
   • a[start] + a[end] = x 만족한다면,
     • 카운트 증가,
     • 같은 원소를 재사용할 필요가 없다. => start는 +1, end는 -1
   • a[start] + a[end] > x를 만족한다면
     • 합이 x보다 크므로 합을 줄여야 한다. => end를  -1
   • a[start] + a[end] < x 만족한다면,
     • 합이 x보다 작으므로 합을 키워야 한다. => start를 +1

private static int toPoint(int start, int end) {
    int result = 0;
    while (start < end) {
        int sum = nums[start] + nums[end];
        if (sum == x) {
            result++;
            start++;
            end--;
        } else if (sum > x) {
            end--;
        } else {
            start++;
        }
    }
    return result;
}

 

 

코드

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int n;
    static int[] nums;
    static int x;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        x = Integer.parseInt(br.readLine());

        Arrays.sort(nums);
        int result = toPoint(0, n - 1);
        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }

    private static int toPoint(int start, int end) {
        int result = 0;
        while (start < end) {
            int sum = nums[start] + nums[end];
            if (sum == x) {
                result++;
                start++;
                end--;
            } else if (sum > x) {
                end--;
            } else {
                start++;
            }
        }
        return result;
    }
}