[3273] 두수의 합 - 투포인터 (백준, 자바, java)

 

 

N이 최대 100_000임

시간 복잡도는 잘 구했다 ! O(N), O(NlogN) 가능.

 

1차 시도)

list에 X - 입력수를 넣어놓고 그 다음에 들어오는 수부터 list.contains(inputNum)으로 찾았더니 시간초과가 났다.

 

2차 시도)

리스트를 없애고 배열로 했는데 메모리 초과가 났다.

숫자를 저장할 배열의 크기를 실수로 너무 크게 지정했다.

숫자의 값 자체를 인덱스로 쓸 것이기 때문에 1,000,001로 지정해주면 될 것이라고 생각했는데 틀렸다.

배열에 저장할 값은 X - 입력값이기 때문에 X가 2,000,000이고 입력값이 1일경우

1,999,999 인덱스에 1을 저장해야 할 텐데 오류남. 따라서 숫자를 체크할 배열 크기는 [2,000,001]로 지정.

 

▶️CountingArray 풀이

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] arr = new int[2_000_001];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int x = Integer.parseInt(br.readLine());
        
        int answer = 0;
        
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            
            if (x - num > 0 && arr[x - num] == 1) {
                answer++;
            }
            arr[num] = 1;
        }
        System.out.println(answer);
        br.close();
    }
}

 

 

통과는 했시만 정석은 투 포인터로 푸는 것이라고 한다.

 

▶️투포인터 풀이

미리 배열을 정렬해두고 시작해야한다.

p1 : 배열의 시작점.

p2 : 배열의 끝점.

p1 + p2 가 key(X) 값보다

 

- 크면 p2를 -1하고

- 작으면 p1을 +1 한다.

- 같으면  answer++하고 다음 값부터 다시 계산해야하기 때문에 p1 ++, p2-- 한다.

두 수는 서로 달라야하므로 p1 < p2인 조건에서 계속해서 반복.

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int x = Integer.parseInt(br.readLine());
        
        int answer = 0;
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int p1 = 0;
        int p2 = n - 1;
        
        while (p1 < p2) {
            int sum = arr[p1] + arr[p2];
            if (sum > x) {
                p2--;
            }
            if (sum < x) {
                p1++;
            }
            if (sum == x) {
                p1++; p2--;
                answer++;
            }
        }
        System.out.println(answer);
        br.close();
    }
}