[Algorithm] 두 배열 합치기

두 배열 합치기

설명

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

입력

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

출력

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

예시 입력 1

3
1 3 5
5
2 3 6 7 9

예시 출력 1

1 2 3 3 5 6 7 9

---

해결

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

public class Main {
    public ArrayList<Integer> solution(int n, int m, int[] array1, int[] array2) {
        ArrayList<Integer> answer = new ArrayList<>();
        int pos1=0, pos2=0;

		// array1, array2 중 한 쪽이라도 배열의 크기 범위를 넘으면 종료 
        // 종료 안하면 ArrayIndexOutOfBoundsException 문제 발생
        while (pos1<n && pos2<m) {
            if (array1[pos1] > array2[pos2]) {
                answer.add(array2[pos2]);
                pos2++;
            } else if (array1[pos1] < array2[pos2]) {
                answer.add(array1[pos1]);
                pos1++;
            } else {
                answer.add(array1[pos1]);
                answer.add(array2[pos2]);
                pos1++;
                pos2++;
            }
        }

		// array1의 원소가 남아있음 -> 남은 원소들 뽑아내기
        while (pos1<n) {
            answer.add(array1[pos1]);
            pos1++;
        }
        // array2의 원소가 남아있음 -> 남은 원소들 뽑아내기
        while (pos2<m) {
            answer.add(array2[pos2]);
            pos2++;
        }
        
        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int[] array1;
        int[] array2;

        int N = Integer.parseInt(br.readLine());
        array1 = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i=0; st.hasMoreTokens(); i++) {
            array1[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        array2 = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i=0; st.hasMoreTokens(); i++) {
            array2[i] = Integer.parseInt(st.nextToken());
        }

        for (int i : T.solution(N, M, array1, array2)) {
            System.out.print(i + " ");
        }
    }
}

• 투 포인터로 해결하는 문제
• 두 배열을 합친 후, 정렬하는 방법도 있지만, 투 포인터 알고리즘을 통해 시간 복잡도를 더 최적화하기 위한 방법이라고 한다
  • 다양한 알고리즘 접해보기ㅣ
• 두 개의 포인터 변수를 통해 두 배열을 순회하며 오름차순으로 정렬했다.
  • pos1, pos2

---

삽질

//        for (int i=0; i<array1.length+array2.length; i++) {
//            if (array1.length > pos1) {
//                answer.add(array2[pos2]);
//                pos2++;
//            }
//            if (array2.length > pos2) {
//                answer.add(array1[pos1]);
//                pos1++;
//            }
//
//            if (array1[pos1] > array2[pos2]) {
//                answer.add(array2[pos2]);
//                pos2++;
//            } else if (array1[pos1] < array2[pos2]) {
//                answer.add(array1[pos1]);
//                pos1++;
//            } else {
//                answer.add(array1[pos1]);
//                answer.add(array2[pos2]);
//                pos1++;
//                pos2++;
//            }
//        }

• 처음엔 while문이 아닌 for문으로 접근했는데, 계속 ArrayIndexOutOfBoundsException가 발생했다.
  • 자꾸 배열의 크기를 벗어난 범위의 포인터로 접근했기 때문이었다.
  • for문이 아닌 while문으로, 한 쪽 배열의 순회가 끝나면, while문을 통해 남은 배열의 원소를 뽑아오는 형태로 해결했다.