[투 포인터] 주몽의 명령

목차

1. 풀이

(1) 문제

백준 1940번, 주몽 : https://www.acmicpc.net/problem/1940

 

핵심 키워드

- 재료의 개수 N(1 ≤ N ≤ 15,000)

- 갑옷을 만드는 데 필요한 수 M(1 ≤ M ≤ 10,000,000)

- 재료에 부여된 고유한 번호와 두 재료의 고유한 번호를 합쳐서 M이 되면 갑옷이 만들어진다.

 

(2) 풀이

• 재료의 개수만큼 배열을 생성하고 투 포인터를 활용해 문제에 접근한다.
• 재료의 고유한 번호는 랜덤으로 입력되는 데, 고유 번호를 입력받은 순서대로와 고유 번호를 오름차순으로 정렬하고 푸는 방법이 있다.
• 정렬(Sort) 알고리즘의 시간복잡도는 O(nlogn)이지만 N의 최대 범위가 15,000 이므로 사용해도 문제가 없다.

고유 번호를 입력받은 순서대로

고유 번호 오름차순으로 정렬

2. 정답

정답 1, 고유번호 정렬 X

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

public class 주몽의명령_1 {
    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[] nums = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;
        int start = 0;
        int end = 1;

        while (start < N) {
           int sum = nums[start] + nums[end];
           if ( end == N) {
               start++;
               end = start + 1;
           } else {
               if ( sum == M) {
                   count++;
                   start++;
                   end = start + 1;
               } else {
                   end++;
               }
           }
        }

        System.out.println(count);
    }
}

• 투 포인터 이동 원칙

두 고유 번호의 합이 M보다 작을 경우 : end++;
두 고유 번호의 합이 M과 같을 경우 : start++; end = start + 1; count++; // end 포인터를 start+1 지점으로 돌아가는 게 핵심

 

정답 - 2, 고유번호 정렬 O

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

public class P1940_주몽 {
    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[] nums = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);
        int count = 0;
        int start = 0;
        int end = N - 1;

        while (start < end) {
            int sum = nums[start] + nums[end];
            if (sum < M) {
                start++;
            } else if (sum > M) {
                end--;
            } else {
                count++;
                start++;
                end--;
            }
        }

        System.out.println(count);
    }
}

• 투 포인터 이동 원칙(고유번호 오름 차순 정렬 후)

start = 0; // 첫번째 포인터, 배열 처음 부분에 위치
end = N-1; // 두번째 포인터, 배열 끝 부분에 위치

sum = A[start] + A[end]; 
sum > M : end--;
sum < M : start++;
sum = M : count++; start++; end--;

3. 참고

- Do it 알고리즘 코딩 테스트 자바 편(김종관)