[코딩테스트] [11728] 배열 합치기

[11728] 배열 합치기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1.5 초

256 MB

46953

22424

14928

46.484%

문제

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

입력

첫째

줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

출력

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

문제풀이

이 문제는 정렬된 두 배열을 주고 하나의 배열로 합치는데 다시 정렬하면 된다.

처음에는 TreeSet을 사용하여 문제를 풀었지만 중복을 제거하면 안된다.

0. 입력받기

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] A = new int[N];
        int[] B = new int[M];
        for (int i = 0; i < N; i++)
            A[i] = sc.nextInt();
        for (int i = 0; i < M; i++)
            B[i] = sc.nextInt();

1. A와 B중 더 작은 값을 정답 배열에 넣기

이미 A와 B는 모두 정렬 되어 있는 상황이다. 그러면 A의 제일 적은 값과 B의 제일 적은값을 비교해주면된다.

두 배열 중 하나가 모두 정렬될때까지 비교를 계속한다.

        int[] ans = new int[N + M];
        int indexA = 0;
        int indexB = 0;
        int indexAnswer = 0;

        while(indexA < N && indexB < M) {
            if (A[indexA] < B[indexB])
                ans[indexAnswer++] = A[indexA++];
            else  ans[indexAnswer++] = B[indexB++];
        }

2. indexA가 N보다 커지거나 indexB가 M보다 커지면 남은 배열값 모두 넣기

혹시 A의 배열이 N번만큼 순회하였거나 B의 배열이 M번만큼 순회하였으면 while문이 종료되어 남은 배열은 모두 넣어주면된다.

        while(indexA < N) ans[indexAnswer++] = A[indexA++];
        while(indexB < M) ans[indexAnswer++] = B[indexB++];

3. 출력하기

이 문제는 출력이 10^9 * 10^9이 될 수 있다. 그래서 BufferedWriter를 사용해야 한다.

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int x: ans)
            bw.write(x + " ");
        bw.write("\\n");
        bw.flush();

시간복잡도

이 알고리즘의 시간복잡도는 O(N + M)이다.