[백준 2018번, 1940번] 투 포인터(Java)

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

 

 

 

006. 연속된 자연수의 합 구하기(백준 2018번)

 

N의 최댓값이 10,000,000으로 매우 크게 잡혀있다.

이런 상황에서는 O(nlogn)의 시작 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로

O(n)의 시간 복잡도 알고리즘을 사용해야 한다.

이런 경우 자주 사용하는 방법이 투 포인터이다.

 

 

이런식으로 end_index가 n이 아닐 때까지 두 포인터를 옮겨가면서 진행하면 된다. 

start_index와 end_index가 각각 최대 N번 움직이므로

전체적으로 2N번의 연산이 발생한다.

빅 오 표기법에서는 상수 계수를 무시하므로, 시간 복잡도는 O(N)으로 표현된다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int sum = 1;
        int count = 1;
        int start_index = 1;
        int end_index = 1;

        while(end_index != n) {
            if(sum == n) {
                count++;
                end_index++;
                sum += end_index;
            } else if (sum > n) {
                sum -= start_index;
                start_index++;
            } else {
                end_index++;
                sum += end_index;
            }
        }
        System.out.println(count);
    }
}

 

 

 

 

007. 주몽의 명령(백준 1940번)

 

먼저, 시간 복잡도를 고려해보면, N의 최대 범위가 15,000이므로

O(nlogn) 시간 복잡도 알고리즘을 사용해도 문제가 없다.

두 재료의 번호의 합, 즉, 크기를 비교하므로 값을 정렬하면 문제를 더 쉽게 풀 수 있다.

입력받은 N개의 재료를 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정하면 된다.

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());
        }
        Arrays.sort(arr);

        int count = 0;
        int i = 0; // arr[0]
        int j = n-1; // arr[n-1]
        while(i<j) {
            if(arr[i] + arr[j] == m) {
                count++;
                i++; j--;
            } else if(arr[i] + arr[j] < m) {
                i++;
            } else {
                j--;
            }
        }
        System.out.println(count);
    }
}