자바 [Algorithm] 투포인터 - 백준 11728 배열 합치기

1. 문제

 

2. 접근법

이 문제는 정렬로 간단하게 풀 수 있다.

int[] arr = new int[N+M]으로 선언하고 arr배열에 A의 배열과 B 배열의 값을 넣고

Arrays.sort를 사용하면 쉽게 풀리지만

 

투포인터를 공부해야 하기 때문에 투포인터로 푼다.

 

1. A의 배열의 포인터와 B의 배열의 포인터를 선언

2. A의 값과 B의 값을 비교하여 오름차순으로 result 배열에 넣는다.

3. 예제 2번처럼 둘의 배열의 크기가 같지 않아 어느 배열의 뒷 값들이 남을 수 있기에 이를 처리한다.

 

3. 코드

package week10;

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

public class Baek11728 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());
        int[] one = new int[N];
        int[] two = new int[M];
        int[] result = new int[N+M];
        int one_point = 0;
        int two_point = 0;
        int a = 0;

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            one[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < M; i++) {
            two[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        while (one_point < N && two_point < M) {
            if (one[one_point] <= two[two_point]) {
                result[a++] = one[one_point++];
            } else {
                result[a++] = two[two_point++];
            }
        }

        //인덱스가 남아있는 경우도 고려
        while (one_point < N) {
            result[a++] = one[one_point++];
        }

        while (two_point < M) {
            result[a++] = two[two_point++];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < result.length; i++) {
            sb.append(result[i]).append(' ');
        }
        System.out.println(sb.toString().trim());

    }
}

 

4. 오답

 

출력 부분에서 시간 초과가 나서 StringBuilder를 사용하니 통과했다.