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

투 포인터 알고리즘이란

배열에서 두 개의 포인터(인덱스)를이용하여 원하는 결과를 얻는 이론입니다.

 

딱히 특별한 알고리즘보다는 코딩 테스트에서 사용할 수 있는 유용한 팁에 가깝습니다.

2018번

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

• 입력: 첫 줄에 정수 N이 주어진다.
• 출력: 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오.

연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현하겠습니다.

시작 인덱스와 종료 인덱스를 투 포인터로 지정해봅시다.

 

손으로 풀어보기

N =15라고 해보고 다음 그림처럼 1~15까지의 숫자를 모두 적어봅시다.

어떤 자연수들의 합으로 15를 만드려면 15보다 작은 숫자들로 구성되어야 하기 때문입니다.

 

두 개의 포인터 start_index와 end_index를 모두 첫 번째 원소에서 시작합니다.

그리고 sum = 1, count = 1로 초기화합니다.

 

이때 sum은 start_index부터 end_index까지의 합이고, count는 연속된 자연수의 합으로 나타내는 가지수입니다.

count가 0이 아니라 1에서부터 시작하는 이유는 '15'라는 자연수 하나만 있어도 연속된 자연수의 합으로 15를 표현하기 때문입니다.

즉, 자기 자신만 있을 때도 답으로 포함되기 때문에 1부터 카운트합니다.

 

 

start_index와 end_index를 움직여가며 합을 15로 만들어봅시다.

이때 start_index와 end_index 투 포인터의 이동은 다음과 같은 원칙을 따릅니다.

• sum > N: sum = sum - start_index; start_index++;
  • sum이 N보다 크다면 작은 수부터 제외한다. start_index를 오른쪽으로 한 칸 옮긴다.
• sum < N: end_index++; sum = sum + end_index:
  • sum이 N보다 작다면 큰 수를 하나 더한다. end_index를 오른쪽으로 한 칸 옮긴다.
• sum == N: end_index++; sum = sum + end_index++; count++;
  • sum이 N과 같다면 연속된 수의 합으로 N을 표현하 조합을 하나 찾은 것이다. count를 올리고, 다음 조합을 찾기 위해 end_index를 한 칸 옮기자.

 

 

 

처음에 sum = 1, start_index = 1, end_index = 1로 시작했다.

sum < 15(N)이므로 end_index를 하나씩 늘린다.

 

end_index = 5가 될 때, 1 + 2 + 3 + 4 + 5 = 15로 sum = 15가 된다. 이때 count가 증가된다.

이후 원칙에 따라 계속 반복한다.

 

반복문은 언제 끝이 날까?

end_index = N이 되는 순간 처음에 구했던 조합 '15'에 달하므로 끝이 난다.

 

import java.util.*;

class Main {
	public static void main(String[] args) {
    	Scanner s = new Scanner(System.in);
        
        int N = s.nextInt();
        int[] arr = new int[N];
        for(int i = 1; i<=N; i++) {
        	arr[i-1] = i;
        }
        
        int sum = 1;
        int start_index = 1;
        int end_index = 1;
        int count = 1;
        
        while(end_index != N) {
        	if(sum > N) {
            	sum -= start_index;
                start_index++;
            }
            if(sum < N) {
                end_index++;
                sum += end_index;
            }
            if(sum == N) {
                end_index++;
                sum += end_index;
                count++;
            }
        }
        System.out.println(count);
    }
}

 

---

1940번

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

• 입력: 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.
• 출력: 첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

 

예제에서 세 번째 줄의 숫자 6개 중 2개의 합으로 9를 만들어낼 수 있는 조합은

(2, 7), (4, 5)로 2개입니다.

 

두 개의 숫자를 뽑고 그 합이 M과 같은지 비교해야겠지요. 이처럼 크기를 비교할 때는 정렬을 하면 문제를 더 쉽게 풀 수 있다고 합니다.

우선, 어떤 정렬을 해도 될지 확인해봅시다.

시간 복잡도 O(nlogn) 알고리즘을 쓴다고 할 때 N의 최대 범위가 15,000이므로 15,000log15,000 ≃210,000 정도 합니다.

즉 1초에 210,000번의 연산을 해야 한다는데 보통의 플랫폼에서는 1초에 약 1억 번의 연산까지 감당 가능하므로 괜찮을 것 같네요.

 

정렬 후, 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근해봅시다.

 

{2, 7, 4, 1, 5, 3}을 정렬하면 {1, 2, 3, 4, 5, 7} 입니다.

 

여기서 투 포인터는 어떻게 이동해야 할까요?

처음은 왼쪽 끝에서 시작하는 인덱스를 i, 오른쪽 끝에서 시작하는 인덱스를 j라고 합시다.

• A[i] + A[j] > M: j--;  // 번호의 합이 M보다 크므로 큰 번호 인덱스를 내립니다.
• A[i] + A[j] < M: i++;  // 번호의 합이 M보다 작으므로 작은 번호 인덱스를 올립니다.
• A[i] + A[j] == M: i++; j--; count++; // 양쪽 포인터를 모두 이동시키고 count를 증가시킵니다.

위 과정을 반복하면 됩니다.

언제까지 반복하면 될까요? i==j가 되면 모든 조합을 살펴봤다는 뜻이니 그때 끝내면 됩니다.

단 i++, j--를 같이 하다보니 안전하게 i!=j 조건 대신 i<j 조건으로 반복문을 합시다.

 

import java.util.*;

class Main {
	public static void main(String[] args) {
    	Scanner s = new Scanner(System.in);
        
        int N = s.nextInt();
        int M = s.nextInt();
        int[] arr = new int[N];
        for(int i=0;i<N;i++) {
        	arr[i] = s.nextInt();
        }
        
        Arrays.sort(arr);
        
        int i = 0;
        int j = N-1;
        int count = 0;
        
        while(i < j) {
        	int sum = arr[i] + arr[j];
            if(sum > M) {
             j--;
            }
            if(sum < M) {
             i++;
            }
            if(sum == M) {
             i++;
             j--;
             count++;
            }
        }
        System.out.println(count);
    }
}

---

Do it! 알고리즘 코딩테스트 with JAVA 강의 내용입니다.