[인프런] 03-01 두 배열 합치기

📖  문제

---

• 첫 번째 줄에 배열의 크기인 N 입력
  • 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어진다.
• 세 번째 줄에 배열의 크기인 M 입력
  • 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어진다
• 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하시오.

출력 예시

 

 

⚠️  주의사항

 

---

• N개의 배열 원소, M개의 배열 원소 오름차순이다.
• 두 배열을 합친 배열도 오름차순이다.

 

✍️  이해

---

• 내가 풀 때 적었던 풀이 방법

* 1. 1차원 배열 입력 2개 받기 N개와 M개
* 2. 한개로 합쳐서 내림차순 해야 하므로 answer[N+M] 에 각각 누적시킨다
*  2-1. N은 i = 0  ~ N -> answer[i]
*  2-2. M은 i = N ~ N+M -> answer[i]
*   2-2-1. M의 값을 answer[i]에 넣을 때 M[i-N] 해줘야 한다 M[0] ~ M[M-1]이 들어가야 하기 때문에
*  2-3. Arrays.sort(배열) -> return 배열

 

• 강의 들으면서 적었던 풀이 방법 (pointer)

* 1. a {1, 3 , 5}  // b {2, 3, 6 ,7, 9}
* 2. a의 p1 과 b의 p2값 비교 (pointer)
*  2-1. p1 < n // p2 < m
*  2-2. 둘 중에 낮은 곳의 p값은 증가 ? 같은 값일 때는? 어떻게?
*  2-3. p1 or p2 가 최댓값 까지 가면 나머지 남은 배열을 그대로 추가

---

위에 풀이 방법이 두 개가 존재하는데 어느 게 더 빠르냐 보다는 두 개의 방법 할 줄 알아야 한다고 생각한다.

그래도 목차 이름이 pointer이니 후자의 방법으로 하도록 노력해볼려고 합니다.

 

✏️  풀이

---

• 직접 풀어 본 풀이 (지양하는 풀이)

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

/**
 * 1. 1차원 배열 입력 2개 받기 N개와 M개
 * 2. 한개로 합쳐서 내림차순 해야 하므로 answer[N+M] 에 각각 누적시킨다
 *  2-1. N은 i = 0  ~ N -> answer[i]
 *  2-2. M은 i = N ~ N+M -> answer[i]
 *   2-2-1. M의 값을 answer[i]에 넣을 때 M[i-N] 해줘야 한다 M[0] ~ M[M-1]이 들어가야 하기 때문에
 *  2-3. Arrays.sort(배열) -> return 배열
 */

public class Java03_01 {

    public int[] solution(int N, int M, int[] arr1, int[] arr2) {

        int length = N + M; // answer 배열 길이
        int[] answer = new int[length];

        for (int i = 0; i < N; i++) { // N의 배열 추가
            answer[i] = arr1[i];
        }

        for (int i = N ; i < length; i++) { // M의 배열 추가
            answer[i] = arr2[i-N];
            // arr2[i] 아닌 이유 -> 예) i = 3 ~ 8 까지 가는데
            // 우리가 원하는 값은 arr2[0] ~ arr[M-1] 이기때문
        }
        Arrays.sort(answer);

        return answer;
    }

    public static void main(String[] args) throws IOException {

        Java03_01 T = new Java03_01();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N개의 배열 입력
        int N = Integer.parseInt(br.readLine());
        int[] arr1 = new int[N];
        StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr1[i] = Integer.parseInt(st1.nextToken());
        }

        // M개의 배열 입력
        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        int[] arr2 = new int[M];
        for (int i = 0; i < M; i++) {
            arr2[i] = Integer.parseInt(st2.nextToken());
        }

        for (int x : T.solution(N, M, arr1, arr2)) System.out.print(x+" ");
    }
}

• ---

  pointer 풀이 (지향하는 풀이)

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

/**
 * 1. a {1, 3 , 5}  // b {2, 3, 6 ,7, 9}
 * 2. a의 p1 과 b의 p2값 비교 (pointer)
 *  2-1. p1 < n // p2 < m
 *  2-2. 둘 중에 낮은 곳의 p값은 증가 ? 같은 값일 때는? 어떻게?
 *  2-3. p1 or p2 가 최댓값 까지 가면 나머지 남은 배열을 그대로 추가
 */

public class Main {

    public ArrayList<Integer> solution (int n, int m, int[] a, int[] b) {
        ArrayList<Integer> answer = new ArrayList<>();
        int p1 = 0, p2 = 0;

        while (p1 < n && p2 < m) { // 둘 중 하나라도 최댓값을 넘어가면 while문 종료
            if (a[p1] < b[p2]) answer.add(a[p1++]);  // 후이증감 연산자 // 전지증감 연산자
                // answer.add(a[p1++]) 할 경우 p1의 해당하는 값 add 해준 뒤 p1++
                // answer.add(a[p1]); p1++ 과 같음
            else answer.add(b[p2++]);
        }

        while (p1<n) answer.add(a[p1++]);
        while (p2<m) answer.add(b[p2++]);

        return answer;
    }

    public static void main(String[] args) throws IOException {

        Main T = new Main();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N개의 배열 입력
        int N = Integer.parseInt(br.readLine());
        int[] arr1 = new int[N];
        StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr1[i] = Integer.parseInt(st1.nextToken());
        }

        // M개의 배열 입력
        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        int[] arr2 = new int[M];
        for (int i = 0; i < M; i++) {
            arr2[i] = Integer.parseInt(st2.nextToken());
        }

        for (int x : T.solution(N, M, arr1, arr2)) System.out.print(x+" ");
    }
}

---

 

출력 화면