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

투포인터 문제

1차 시도

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


public class BOJ_3273_두수의합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        int x = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < line.length; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(arr);
        int left = 0;
        int right = 1;
        int result = 0;
        while (left < n - 1) {
            while (right < n - 1) {
                if (arr[right] + arr[left] != x) {
                    right++;
                } else {
                    left++;
                    result++;
                    break;
                }
            }
        }
        System.out.println(result);
    }
}

무한 루프에 빠짐. => 뭔가 논리에 오류가 있는듯하다ㅜ

2차 시도

public class BOJ_3273_두수의합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        int x = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < line.length; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(arr);
        int left = 0;
        int right = 1;
        int result = 0;
        while (left < n - 1) {
            if (arr[right] + arr[left] < x) {
                right++;
            } else if (arr[right] + arr[left] == x) {
                left++;
                right = left + 1;
                result++;
            } else {
                left++;
            }

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

수정사항

• 내부 루프가 잘못되었었다. 작성하면서도 뭔가 이상하다는 느낌이 들었는데 역시나 그랬다.
• 이중 loop 를 사용하기 보다, arr[right] + arr[left] > x 일 경우도 추가 고려하면 좋다.
• 또 right 는 초기화 시 항상 left+1 임을 숙지하자!

But, 아직도 문제 발생..!

3차 시도

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


public class BOJ_3273_두수의합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        int x = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < line.length; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(arr);
        int left = 0, right = 1, result = 0;
        while (left < n - 1) {
            if (right >= n) {     //right 가 끝에 닿으면 재설정
                left++;
                right = left + 1;
                continue;
            }
            int sum = arr[left] + arr[right];
            if (sum == x) {
                left++;
                result++;
                right = left + 1;
            } else if (sum < x) {
                right++;
            } else {
                left++;
                right = left + 1;
            }

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

수정사항

right 의 재설정

• arr[right] + arr[left]> x인 경우 왼쪽은 증가시키지만(left++) 오른쪽은 재설정하지 않았다.
• 이러면 오른쪽이 재설정되지 않고 배열의 끝(n)에 도달하여 유효한 쌍이 누락될 수 있다.

=> 시간초과로 실패..

• 현재 내 시간복잡도는 투포인터 요소찾기 O(n), 정렬로인해 O(nlogn). 따라서 O(nlogn).

4차 시도

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


public class BOJ_3273_두수의합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        int x = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < line.length; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(arr);
        int left = 0, right = n-1, result = 0;
        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == x) {
                left++;
                right--;    // 중복 없음으로 left 를 증가시켰음으로 sum ==x 되려면 Right 를 감소시켜야 hit 확률 up
                result++;
            } else if (sum < x) {
                left++;
            } else {  //더 크다면
                right--;
            }
        }
        System.out.println(result);
    }
}

수정사항

• 경로를 다 돌지말고, left 를 증가시키고, right 를 줄이면서 포위망을 계속 좁히자.