💚 백준 1940 주몽

1. 문제 분석

문제 링크

N개의 수 중 2개를 뽑아서 그게 M과 맞는지 계산하면 된다고 생각했다.
그래서 조합을 사용했다. N이 15000개까지 주어진다. 15000C2 = 112492500 이다.
주어진 시간이 2초임으로 20억 번의 계산이 가능한 상황에서 11억의 계산은 Safe다. 따라서 단순 조합을 해도 문제는 풀린다. (시간이 오래 걸렸지만...)
나는 DO IT! 알고리즘 코딩테스트 책에서 소개한 투 포인터로도 문제를 풀어 보았다. 투 포인터를 쓰면 정렬 후 최대 N+1 번의 연산이 필요해서 총 N+1 +NlogN = O(NlogN) 의 시간이 든다.
이걸 N의 최대 값인 15000으로 계산해보면, 15000 * log(15000) = 62641 개의 연산만 하면 되어서 훨씬 빠르다.

두 방법 다 소개해보겠다.

2. 푸는 원리

ⓐ 조합

N개 중 2개를 뽑았을 때, 두 수의 합이 M이 되는지를 계산한다.

ⓑ 투 포인터

1. 먼저 주어진 수들을 배열에 넣고 정렬한다.
2. 포인터를 배열 맨 왼쪽(최소값), 맨 오른쪽(최대값)에 둔다.
3. 두 포인터가 가르키는 원소의 합이 M보다 작으면 오른쪽 포인터를 중앙으로 한 칸 당긴다.
4. M보다 크면 왼쪽 포인터를 중앙으로 당긴다.
5. 두 포인터가 만날 때까지 반복한다.
   1번 loop (1 + 8 < 9)

1번	2번	3번	4번	5번	6번
1	2	3	4	5	7
s					e

2번 loop(2 + 7 = 9 (cnt 카운트) )

1번	2번	3번	4번	5번	6번
1	2	3	4	5	7
	s				e

왜 정렬 해야할까?

정렬을 해야지 M과 포인터 합들간의 수 비교가 예상이 가고 내가 제어할 수 있다. 따라서 코드를 짤 수 있는 것이다.
(왼쪽 포인터를 올리면 합이 커진다. 오른쪽 포인터를 내리면 값이 작아진다. 등)

3. 코드 분석

ⓐ 조합

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


/*
 * 1940번 주몽
 * */


public class Main {

    static int N, M;
    static int [] arr;
    static int [] target = new int [2];
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 1. 값 받기
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        arr = new int[N];

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

        combination(0,0);
        System.out.println(cnt);
    }

    public static void combination (int depth, int start) {
        if(depth == 2){

            int ans = 0;
            for (int i = 0; i < target.length; i++) {
                ans +=target[i];
            }
            if(ans == M) {
                cnt ++;
            }
            return;
        }

        for (int i = start; i < N; i++) {
           target[depth] = arr[i];
           combination(depth+1, i+1);
        }
    }
}

ⓑ 투 포인터

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


/*
 * 1940번 주몽
 * */


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());
        }

        Arrays.sort(arr);

        int start = 0, end = N-1, cnt = 0;

        while (start != end) {
            int value = arr[start] + arr[end];

            if(value > M){
                end--;
            } else if (value == M) {
                cnt ++;
                end --;
            } else {
                start ++;
            }
        }

        System.out.println(cnt);

    }
}