[Java] 백준 1940 주몽

https://www.acmicpc.net/problem/1940

예제입력

6
9
2 7 4 1 5 3

예제출력

2

설명
이번 문제는 투 포인터 알고리즘으로 풀 수 있다.

포인터를 두개를 두고 해결하는 알고리즘이며, 방법은 이렇다.

갑옷을 만드는데 필요한 수 = m
i + j < m : i++
i + j > m : j--
i + j == m : count++ i++ j--

이 방법으로 갑옷 수를 구하려면 배열이 정렬되어 있어야 하므로 정렬한 뒤 방법을 적용해보자.

코드

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

        long n = Integer.parseInt(br.readLine());
        long m = Integer.parseInt(br.readLine());
        long[] arr = new long[(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;
        // 배열의 끝
        int j = (int) (n -1);

        while (i < j) {
            if (arr[i] + arr[j] < m) {
            	// i 를 한칸 당겨 숫자를 키운다
                i++;
            } else if (arr[i] + arr[j] > m) {
            	// j 를 앞으로 당겨 숫자를 작아지게 한다
                j--;
            } else if (arr[i] + arr[j] == m) {
            	// 해당 숫자를 찾았으므로 i 와 j 를 한칸씩 당긴다.
                i++; j--; count++;
            }
        }
        System.out.println(count);
    }
}