[JAVA] 백준 1940번 : 주몽

https://www.acmicpc.net/problem/1940
이 문제도 투포인터 문제이다.

이 문제에서 sum == M인 경우 start와 end값을 조율해 주어야 하는 로직을 생각 하는 것이 살짝 시간이 걸렸다.

문제의 예시처럼 2, 7, 4, 1, 5, 3을 예시로 들어보자. 이것을 정렬하면 1, 2, 3, 4, 5, 7이 되는데, 이 때 합을 구하면 5가 되는 것을 생각해보자. 내가 1 + 4로 5를 만들고 나면, 그 사이에 있는 2 + 3을 구해야 한다. 그렇기 때문에 start index는 1을 증가시키고, end index는 1을 감소시켜야 한다.

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

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()); //갑옷을 만드는 데 필요한 수
        String[] input = br.readLine().split(" ");
        int[] materials = new int[N]; //재료들이 가진 고유한 번호

        for (int i = 0; i < N; i++) {
            materials[i] = Integer.parseInt(input[i]);
        }

        int cnt = 0;
        Arrays.sort(materials); //투포인터를 사용하기 위하여 정렬

        int start = 0; //시작 index
        int end = N - 1; //끝 index

        while (start < end) {
            int sum = materials[start] + materials[end];
            if (sum == M) { //합계과 M과 같으면
                cnt++; //횟수 증가
                start++;
                end--;
            } else if (sum < M) { //합계가 더 작으면 시작 값을 늘려 합계가 커지도록 함
                start++;
            } else if (sum > M) { //합계가 더 크면 끝 값을 줄여 합계가 작아지도록 함
                end--;
            }
        }
        System.out.println(cnt);
        br.close();
    }
}