[알고리즘] 두 배열 합치기 - Two Pointers

문제 설명

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

입력

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.

세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.

네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

 

출력

오름차순으로 정렬된 배열을 출력합니다.

예시 입력

3
1 3 5
5
2 3 6 7 9

예시 출력

1 2 3 3 5 6 7 9

 

문제 풀이

두 배열을 합치는 문제이다.

for문을 2번 사용하여 새로운 배열에 넣어주고, Arrays.sort(배열)을 사용하여 문제를 해결하면 간단히 해결할 수 있긴 하다.

 

하지만 Two Pointers 방법으로 해당문제를 풀이해보았다. Two Pointers 배열을 다루는 알고리즘 문제에서 많이 사용하는 방법이다.

해당 문제는 Two Pointers를 이해하기에 쉬운 문제이기에.. 해당 방법을 사용하여 문제를 풀이해보았다.

 

접근 방법은 다음과 같다.

A. 두 배열에 해당하는 각각의 인덱스를 변수로 선언.

B. 두 배열에서 인덱스에 해당하는 값을 가져와 비교하고, 더 작은쪽의 값을 저장한다. (오름차순 정렬을 위해)

C. 값을 가져온쪽 배열의 인덱스를 증감해준다.

D. 2번과 3번과정을 반복한다. 단, 한쪽의 배열이라도 배열끝까지 확인했다면 반복을 멈춘다. 

B번단계 반복과정

 

아래는 위 내용을 구현한 코드이다.

List<Integer> answer = new ArrayList<>();

int arr1Index = 0;
int arr2Index = 0;

// 배열의 인덱스1, 인덱스2를 선언하고 answer list에 넣어준 배열의 값만 해당배열인덱스를 증감한다.
while (arr1Index < n1 && arr2Index < n2) {
    answer.add(arr1[arr1Index] < arr2[arr2Index] ? arr1[arr1Index++] : arr2[arr2Index++]);
}

위 과정을 정상적으로 수행했다면, 변수 answer에 1, 2, 3, 3, 5가 저장되고, arr1 배열의 값을 모두 확인하였으므로 반복문이 종료됐을 것이다.

 

arr2 배열의 나머지 데이터를 차례로 넣어주는 작업이 필요하다.

// 배열의 나머지 데이터를 모두 넣어준다. 데이터를 모두 넣어준 배열이라면 해당for문을 실행하지 않음.
for (int i = arr1Index; i < n1; i++) {
    answer.add(arr1[i]);
}

// 배열의 나머지 데이터를 모두 넣어준다. 데이터를 모두 넣어준 배열이라면 해당for문을 실행하지 않음.
for (int i = arr2Index; i < n2; i++) {
    answer.add(arr2[i]);
}

 

두 배열 중 어떤 배열이 먼저 종료되는지 모르므로 두 배열 모두 확인한다.

 

전체 소스

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main m = new Main();

        int n1 = kb.nextInt();
        int [] arr1 = new int[n1];
        for (int i = 0; i < n1; i++) {
            arr1[i] = kb.nextInt();
        }

        int n2 = kb.nextInt();
        int [] arr2 = new int[n2];
        for (int i = 0; i < n2; i++) {
            arr2[i] = kb.nextInt();
        }

        List<Integer> answer = m.solution(n1, n2, arr1, arr2);

        answer.forEach(item -> {
            System.out.print(item + " ");
        });
    }

    public List<Integer> solution(int n1, int n2, int[] arr1, int[] arr2) {
        List<Integer> answer = new ArrayList<>();

        int arr1Index = 0;
        int arr2Index = 0;

        // 배열의 인덱스1, 인덱스2를 선언하고 answer list에 넣어준 배열의 값만 해당배열인덱스를 증감한다.
        while (arr1Index < n1 && arr2Index < n2) {
            answer.add(arr1[arr1Index] < arr2[arr2Index] ? arr1[arr1Index++] : arr2[arr2Index++]);
        }

        // 배열의 나머지 데이터를 모두 넣어준다. 데이터를 모두 넣어준 배열이라면 해당for문을 실행하지 않음.
        for (int i = arr1Index; i < n1; i++) {
            answer.add(arr1[i]);
        }

        // 배열의 나머지 데이터를 모두 넣어준다. 데이터를 모두 넣어준 배열이라면 해당for문을 실행하지 않음.
        for (int i = arr2Index; i < n2; i++) {
            answer.add(arr2[i]);
        }

        return answer;
    }
}