자바(백준) 3273 두 수의 합

오답 노트 & 새로 알게 된 점

이 문제는 이분 탐색으로도 풀었던 문제이다.

투 포인터를 이용해서도 풀 수 있기 때문에 투 포인터 공부할 겸 풀어보았다.

 

당연히 일일이 계산하는 O(N^2) 는 TLE다.

O(N)인 투포인터를 생각하게 되었다. 

 

처음에 여기서 i < j 를 보고 정렬하면 안되는건가? index를 유지하라는 말인가?라고 생각했다.

하지만 그게 아니였고, 단지 중복 계산을 막기 위해서이다.

예로 12 + 1과 1 + 12는 서로 같은 것임을 나타낸 것 같다. (나의 생각)

 

그래서 정렬하고 처음과 끝에서부터 각각 시작하여 투 포인터를 하면 해결할 수 있다.

 

---

 

코드

package TwoPointers;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ3273 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int n, x;
    static int A[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = atoi(br.readLine());
 
        A = new int[n + 1];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= n; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        x = atoi(br.readLine());
 
        Arrays.sort(A);
 
        pro();
    }
 
    static void pro() {
        int s = 1, e = n, cnt = 0;
 
        while (s < e) {
            int sum = A[s] + A[e];
 
            if(sum == x){
                cnt++;
                s++;
                e--;
            }
            else if(sum > x) e--;
            else s++;
        }
        System.out.println(cnt);
    }
}