백준 - 투 포인터 3273번 두 수의 합 / 틀린 이유, 해결 방법 ( 알고리즘 )

= 내 접근 방법 ( 오답 ) =

흔히 사용하던 2중 for문을 사용했기 때문에 오답이다.

 

투 포인터 알고리즘은 언제 사용해야 될까?

문제를 잘 봐야한다.

시간 제한은 1초, n은 1000000이기 때문에

2중 for문을 이용한 단순한 코드는 O(N^2)이기 때문에 시간을 초과한다.

 

이러한 문제에 닥쳤을 때 투 포인터 알고리즘을 이용해서 해결해야 됨!

 

https://byungil.tistory.com/193 이 링크에서 알고리즘에 대한 설명을 써놨다.

 

= 알고리즘을 이용한 접근 ( 정답 ) = 

 

1. 정렬된 배열이 필요.
2. 왼쪽 맨끝 과 오른쪽 맨끝에서 순차적으로 번갈아 가면서 접근

만족 => end-- or start++ 둘 중 하나, count++

두 수의 합이 더 크면 end--

두 수의 합이 더 작으면 start++
3. 인덱스가 교차하게 되는 순간에 종료

 

내가 해왔던 방법은 동시에 같은 index에서 출발이지만

이 문제는 동시에 출발하는 방법이 아닌 양 끝점에서 시작하는 문제다.

여러가지 유형을 접해봐야 문제를 수월하게 풀 수 있을 것 같다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 1. input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 수열의 크기 n
        int[] arr = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); // 수열에 포함되는 수 m
        }
        Arrays.sort(arr);
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken()); // 자연수 x
        // x를 만족하는 쌍의 개수를 출력한다.

        int start = 0;
        int end = n - 1;
        int sum = 0;
        int count = 0;

        while (start < end) {

            sum = arr[start] + arr[end];

            if (sum < x) {
                start++;
            } else if (sum == x) {
                end--;
                count++;
            } else if (sum > x) {
                end--;
            }
        }

        System.out.println(count);
    }
}