백준-3273

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

정답 코드

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args)throws Exception {
        int n,x;
        int a[];
        int count = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         n = Integer.parseInt(br.readLine());
        a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        x = Integer.parseInt(br.readLine());
        //입력
        
        Arrays.sort(a);//정렬
        int start = 0; //시작 포인터
        int end = n-1;// 끝 포인터
        
        while(start < end){ //두 포인터가 겹치면 종료
            if(a[start]+a[end]==x){
                count++; //x 값이 나오는 경우의 수
                start++;
                end--;
              }
            else if(a[start]+a[end]<x){ //x보다 작으면, 두 수 중 값이 작은 수를 다음 인덱스로
                start++;
            }    
            else if(a[start]+a[end]>x){ //x보다 크면, 두 수 중 값이 큰 수를 이전 인덱스로
                end--;
            }
        }
        
        System.out.println(count);
    }
}

틀렸던 코드(런타임 에러)

for (int i = 0; i < a.length; i++) {
            for (int j = a.length-i; j > i; j--) {
                if (a[i] + a[j] == x) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }

후기

투 포인터 방식은 선형으로된 배열을 두 개의 점을 지저하고, 그 위치의 값을 비교하고, 다음 순서를 찾으려는 값에 근접하게 점을 이동 시킨다. 방식은 2개의 점을 어떤 위치에 두냐에 따라 나뉜다.

• 첫 번째는 시작 점과 끝 점이라고 명했을 때, 시작점과 끝점을 나란히 두어 같이 이동하며 찾는 값을 비교한다. 틀렸던 코드가 이 방식이였다.
• 두 번째는 시작 점과 끝 점을 배열의 양 끝에 두어 찾으려는 값을 비교하여 두 점을 점점 인접하게 진행한다.