1940번 문제 링크

투포인터 문제가 나랑 안맞나...??? 이전에 풀었던 포인터 문제와는 또다른 문제였다.

조건의 변수의 범위에 따라서 연산의 총시간을 예상한 뒤 이를 고려한 알고리즘으로 풀어야 하는 것 같다.

두 재료의 요소의 합, 즉 크기를 비교하는 문제이므로 값을 정렬하면 문제를 좀 더 빠르게 풀 수 있다. N의 최대 범위가 15,000 이기 때문에 O(nlogn) 시간 복잡도 알고리즘을 사용해도 큰 상관이 없다. 일반적으로 정렬 알고리즘의 시간 복잡도는 O(nlogn) 이다.

우선 양쪽 끝의 위치를 투 포인터로 지정해 문제를 접근해보면, 다음과 같다

알고리즘
1. 수열을 오름차순으로 정렬한다.
2. 투 포인터를 양 쪽 끝에 위치시킨 뒤 포인터 이동 원칙을 활용하여 탐색을 수행한다.
3. i와 j가 만날때까지 2번 로직을 반복한다. 반복이 끝나면, count를 출력한다.

😀 성공

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

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 M = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        arr = Arrays.stream(arr).sorted().toArray();
        int count = 0, i = 0, j = N-1;
        while(i < j){
            int sum = arr[i] + arr[j];
            if(sum < M){
                i++;
            }
            else if(sum == M){
                i++;
                j--;
                count++;
            }
            else if(sum > M){
                j--;
            }
        }
        br.close();
        System.out.println(count);
    }
}