[백준1940] 주몽 Java

밥은답 2023. 8. 12. 23:07

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

1940번: 주몽

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고

www.acmicpc.net

package Chapter1;
import java.util.*;

public class BJ1940 {
    public static void main(String[] args) {
        // 입력
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }

// 투포인터 알고리즘 사용하기 위해서 배열을 오름차순으로 정렬
        Arrays.sort(arr);

        int lp = 0; // 왼쪽 포인터
        int rp = n-1; // 오른쪽 포인터
        int count = 0;

        while (lp < rp) {
            int sum = arr[lp] + arr[rp];
            if (sum == m) {
                count++;
                rp--;
                lp++;
            }
            else if (sum < m) {
                lp++;
            }
            else {
                rp--;
            }
        }

        System.out.println(count);
    }
}