Java 문제풀이 - 주몽의 명령

문제

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제 입/출력

나의 풀이

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // Find the middle point
            int middle = (left + right) / 2;

            // Sort first and second halves
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);

            // Merge the sorted halves
            merge(arr, left, middle, right);
        }
    }

    private static void merge(int[] arr, int left, int middle, int right) {
        // Find sizes of two subarrays to be merged
        int n1 = middle - left + 1;
        int n2 = right - middle;

        // Create temp arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temp arrays
        for (int i = 0; i < n1; ++i) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[middle + 1 + j];
        }

        // Merge the temp arrays

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of L[] if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Copy remaining elements of R[] if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        // N은 재료들의 갯수, M은 재료들을 합쳐 만들 수
        int N = sc.nextInt();
        int M = sc.nextInt();

        // materials는 재료들의 고유 숫자를 담을 배열
        int[] materials = new int[N + 1];

        for (int i = 1; i < N + 1; i++) {
            int input = sc.nextInt();
            materials[i] = input;
        }

        // 합병 정렬
        mergeSort(materials, 0, materials.length - 1);

        // 투 포인터
        int startIndex = 1;
        int endIndex = N;
        int sum;
        int count = 0;

        while (startIndex < endIndex) {
            sum = materials[startIndex] + materials[endIndex];

            if (sum == M) {
                count++;
                endIndex--;
                startIndex++;
            } else if (sum > M) {
                endIndex--;
            } else if (sum < M) {
                startIndex++;
            }
        }

        System.out.println(count);
    }
}

예제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1940_주몽 {
  public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    int M = Integer.parseInt(bf.readLine());
    int[] A = new int[N];
    StringTokenizer st = new StringTokenizer(bf.readLine());
    for (int i = 0; i < N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(A);
    int count = 0;
    int i = 0;
    int j = N - 1;
    while (i < j) {
      if (A[i] + A[j] < M) {
        i++;
      } else if (A[i] + A[j] > M) {
        j--;
      } else {
        count++;
        i++;
        j--;
      }
    }
    System.out.println(count);
    bf.close();
  }
}

리뷰

예제 풀이에서는 Array.sort()를 사용하여 정렬하고, 나의 경우는 Heap sort를 직접 구현하여 사용하였다.

https://laugh4mile.tistory.com/175

위의 글을 참고하면 Array.sort()는 최악의 경우 O(n^2)의 시간복잡도를 가지는데, 그러면 n의 최대 크기가 15000이므로 최악의 경우 225000000회의 연산, 즉 시간 제한 2초를 넘는다. 그래서 Heap sort를 구현해서 사용한 것이 더 낫지 않나 싶다,