[백준 JAVA] 1940 주몽

1940 주몽

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

문제설명

투 포인터를 사용하여 주어진 재료들 중에서 합이 주어진 M이 되는 경우의 수 구하기

접근방식

O(N log N) 시간복잡도

 

합이 M이 되는 경우의 수를 찾을 때 투 포인터를 이용하고 이후 Arrays.sort()를 이용하여 정렬한다.

Arrays.sort()의 정렬 시간복잡도는 O(N log N)이다. 

전체 시간복잡도는 O(N log N)을 가진다.

문제 조건 분석 과정

 

1. 재료들을 배열에 넣고 정렬한다.

2. 투포인터로 합이 M이 되는 경우의 수를 계산한다.

 

사용된 자료구조

• 배열: Arrays.sort() 배열에 주어진 재료들을 저장하고 이 배열을 정렬한다.
• 투 포인터: left와 right라는 두 개의 포인터를 사용해 조건에 따라 배열을 탐색한다.

전체코드

import java.io.*;
import java.util.*;

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[] materials = new int[N]; // 재료들의 번호 배열

        // 두 번째 줄 입력 처리 (재료들의 고유 번호들)
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            materials[i] = Integer.parseInt(st.nextToken());
        }

        // 재료 번호 배열 정렬
        Arrays.sort(materials);

        int count = 0; // 갑옷을 만들 수 있는 경우의 수
        int left = 0; // 왼쪽 포인터
        int right = N - 1; // 오른쪽 포인터

        // 투 포인터를 이용한 합 검사
        while (left < right) {
            int sum = materials[left] + materials[right];

            if (sum == M) {
                count++;
                left++;
                right--;
            } else if (sum < M) {
                left++;
            } else { // sum > M
                right--;
            }
        }

        System.out.println(count); // 결과 출력
    }
}