자바(백준) 1253 좋다

오답 노트 & 새로 알게 된 점

항상 두 포인터 문제를 풀면 연속 부분 수열, 순서를 지키며 차례대로 라는 말이 문제에서 나왔다.

하지만 이 문제에서는 그러한 힌트가 없었다.

 

그래서 나는 코테에서 이런 문제가 나온다면 내가 풀 수 있을까?라는 생각이 들었다.

 

아마 처음에 접근했을 때는 완탐으로 생각을 할 것이다.

 

그렇다면 타겟을 하나 고르고 -> O(N)

더해서 타겟이 되는 두 수를 구한다 -> O(N^2)

 

그래서 O(N^3)이다. 당연히 TLE가 난다.

 

그렇다면 여기서 어떤 방법을 사용해야 시간 복잡도를 줄일 수 있을까?

 

두 포인터를 사용하여 타겟을 하나 정하고 O(N)

두 수를 정할 때, O(N)을 사용하면 된다.

 

두 수를 정하고

합이 target보다 작으면

최소 입장에선 최대를 더했는데 작기 때문에 s를 늘리고,

 

target보다 크면

최대 입장에선 최소를 더했는데 크기 때문에 e를 줄여야한다.

 

---

 

코드

package TwoPointers;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, cnt;
    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];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        Arrays.sort(A);
 
        for (int i = 0; i < N; i++) {
            pro(i);
        }
        System.out.println(cnt);
    }
 
    static void pro(int idx) {
        int s = 0, e = N-1;
        int target = A[idx];
 
        while (s < e) {
            if(s == idx) s++;
            else if(e == idx) e--;
 
            else {
                if (target > A[s] + A[e]) s++;
                else if (target == A[s] + A[e]) {
                    cnt++;
                    return;
                } else e--;
            }
        }
    }
}