[인프런 알고리즘] Chpater3, 1번 문제(두 배열 합치기)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

첫 번째 코드(정렬 알고리즘을 이용한 방법)

package inflearn_algorithm.chapter3;

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

public class sec03_01 {
    public static int[] solution(int [] arr1, int [] arr2) {
        int[] mergeArr = new int[arr1.length + arr2.length];
        for (int i = 0; i < mergeArr.length; i++) {
            if(i < arr1.length) mergeArr[i] = arr1[i];
            else mergeArr[i] = arr2[i - arr1.length];
        }
        Arrays.sort(mergeArr);

        return mergeArr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr1 = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr1[i] = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        int[] arr2 = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; ++i) arr2[i] = Integer.parseInt(st.nextToken());

        for (int i : solution(arr1, arr2)) System.out.print(i + " ");
    }
}

 

두 번째 코드(투 포인터를 이용한 방법)

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

public class sec03_01 {
    public static int[] solution(int[] arr1, int[] arr2) {
        int[] mergeArr = new int[arr1.length + arr2.length];
        int ptr1 = 0, ptr2 = 0, i = 0;

        while (ptr1 < arr1.length && ptr2 < arr2.length) {
            if (arr1[ptr1] <= arr2[ptr2]) mergeArr[i++] = arr1[ptr1++];
            else mergeArr[i++] = arr2[ptr2++];
        }

        while (ptr1 < arr1.length) mergeArr[i++] = arr1[ptr1++];
        while (ptr2 < arr2.length) mergeArr[i++] = arr2[ptr2++];

        return mergeArr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr1 = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr1[i] = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        int[] arr2 = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; ++i) arr2[i] = Integer.parseInt(st.nextToken());

        for (int i : solution(arr1, arr2)) System.out.print(i + " ");
    }
}

 

설명

두 번째 코드에 대한 설명

• ptr1과 ptr2는 각각 arr1과 arr2의 현재 위치를 가리키며, 두 배열의 끝에 도달할 때까지 반복된다.
• 결과 배열인 mergeArr는 arr1과 arr2의 길이를 합친 크기로 초기화된다.
• 두 배열의 요소를 비교하며 작은 값을 결과 배열에 추가하고, 포인터를 증가시킨다.
• 한 배열의 모든 요소를 처리한 후 다른 배열의 나머지 요소들을 모두 결과 배열에 추가한다.