배열 합치기 - '백준 11728번'

11728번: 배열 합치기

정렬된 두 배열(A, B)이 주어지고, 두 배열을 합쳐서 오름차순으로 정렬 하여 출력 하는 문제 입니다.

 

1. 접근

1.  두 배열을 하나의 배열로 합쳐서, 그 하나의 배열을 Arrays.sort() 함수(Dual-Pivot 정렬 : nLogN 보장)를 사용해서 정렬 후 출력, 하지만, 시간 제한 1.5초에 통과 하기는 쉽지 않습니다.

2. 잘 보면 두 배열이 각각 정렬 되어 있으므로 Merge Sort를 이용해서 시간 복잡도(N)으로 가능 합니다.

3. Merge Sort의 경우 '분할', '병합' 두 부분으로 나눌 수 있는데, '분할'의 경우 logN, '병합'의 경우 N의 시간 복잡도가 걸립니다.

4. 그런데, 두 배열(A, B)가 이미 정렬되어 있으므로, Merge Sort의 merge(병합) 만 진행 하면 시간 복잡도(N) 만의 문제를 해결 할 수 있습니다.

 

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

public class BOJ11728_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(in.readLine());
        int[] A = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(in.readLine());
        int[] B = new int[M];
        for (int i = 0; i < M; i++)
            B[i] = Integer.parseInt(st.nextToken());

        BOJ11728_2 main = new BOJ11728_2();
        main.solution(N, M, A, B);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N + M; i++) {
            sb.append(main.sorted[i]).append(" ");
        }
        out.write(sb.toString());
        out.close();
    }

    // 최종 배열 sorted
    int[] sorted;

    public int[] solution(int N, int M, int[] A, int[] B) {
        this.sorted = new int[N + M];
        merge(A, B, N, M);
        return sorted;
    }

    private void merge(int[] A, int[] B, int N, int M) {
        // A 배열 시작, 끝
        int i = 0;
        int n = N;

        // B 배열 시작, 끝
        int j = 0;
        int m = M;

        // sorted 배열 인덱스
        int k = 0;

        // 앞배열(인덱스 i), 뒷배열(인덱스 j)가 각각 정렬 되어 있음
        while(i < n && j < m) {
            if (A[i] < B[j])
                sorted[k++] = A[i++];
            else
                sorted[k++] = B[j++];
        }

        // A 배열이 다 담겼다면, B 배열 나머지 넣어주기
        while (i < n) sorted[k++] = A[i++];
        while (j < m) sorted[k++] = B[j++];
    }
}

위 소스가 최종 소스 인데요. 저는 '시간 초과'를 몇번 받았습니다. 그래서 입력부와 출력부를 수정 했습니다.

 

 

2. Scanner, Stream API

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
sc.nextLine();

int[] A = Arrays.stream(sc.nextLine().split(" "))
.mapToInt(Integer::parseInt).toArray();
int[] B = Arrays.stream(sc.nextLine().split(" "))
.mapToInt(Integer::parseInt).toArray();

BOJ11728_2 main = new BOJ11728_2();
main.solution(N, M, A, B);

for (int i = 0; i < N + M; i++) {	
	System.out.printf("%d ", main.sorted[i]);
}

제일, 초반 입력, 출력부 소스 코드 입니다. Scanner 를 사용해서 입력을 받았는데, Scanner 는 편하지만, 굉장히 느립니다. 

 

 

3. Scanner -> BufferedReader

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

int[] len = Arrays.stream(bf.readLine().split(" ")).parallel()
.mapToInt(Integer::parseInt).toArray();
int N = len[0];
int M = len[1];

int[] A = Arrays.stream((bf.readLine().split(" "))).parallel()
.mapToInt(Integer::parseInt).toArray();
int[] B = Arrays.stream(bf.readLine().split(" ")).parallel()
.mapToInt(Integer::parseInt).toArray();

따라서, Scanner 대신에 BufferedReader 를 사용했습니다. Scanner 보다 훨씬 빠릅니다. 하지만, 이 소스 코드 역시 '시간 초과' 를 받았습니다. 한동안 고민 후, Stream API를 수정 하였습니다. 구글링 해보니, stream 보다 for-loop 문이 더 빠르다고 나오더군요.

 

 

4. Stream -> for loop

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

int N, M;
String[] len = bf.readLine().split(" ");
N = Integer.parseInt(len[0]);
M = Integer.parseInt(len[1]);

int[] A = new int[N];
String[] AStrs = bf.readLine().split(" ");
for (int i = 0; i < N; i++) {
	A[i] = Integer.parseInt(AStrs[i]);
}

int[] B = new int[M];
String[] BStrs = bf.readLine().split(" ");
for (int i = 0; i < M; i++) {
	B[i] = Integer.parseInt(BStrs[i]);
}

Arrays.stream() -> for-loop 문으로 변경 하였습니다. 하지만, 또 '시간 초과'를 받았습니다. 입력부가 문제가 아니였습니다!

 

 

5. System.out.print() in for -> StringBuilder.toString()

StringBuilder sb = new StringBuilder();
for (int i = 0; i < N + M; i++) {
	sb.append(main.sorted[i]).append(" ");
}
System.out.println(sb.toString());

 

출력부를 수정 했습니다. 원래 System.out.printf("%d ", main.sorted[i]); 이런식으로 출력을 시켜 주었는데, 이것 또한, 배열의 원소 값 만큼 출력 하기에는 굉장히 느립니다. StringBuilder 로 모두 모아서 한번의 출력 시켜줘야 '시간 초과' 에서 벗어 날수 있었습니다. 

 

 

1.7초 로 줄였지만, 하지만, 문제의 시간 제한은 1.5초 입니다. 이것 역시 효율성 테스트에서는 떨어지는 결과 입니다. 이번에는 String.split() 의 성능이 의심스러웠습니다. 검색해본 결과, 지금은 거의 쓰는걸 못본, StringTokenizer 가 빠르다는 걸 알수 있었습니다.

 

 

6. String.split() -> StringTokenizer

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

StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());

st = new StringTokenizer(br.readLine());
int[] A = new int[N];
for (int i = 0; i < N; i++)
	A[i] = Integer.parseInt(st.nextToken());

st = new StringTokenizer(br.readLine());
int[] B = new int[M];
for (int i = 0; i < M; i++)
	B[i] = Integer.parseInt(st.nextToken());

 

결과는 1.2초 1.5초 안으로 들어 올 수 있었습니다.

 

 

여기서, 한가지만 더 해보고 싶었습니다. 

입력부도 Scanner -> BufferedReader로 변경하여 속도 개선을 누렸는데, 출력부도 역시 BufferedWriter로 변경하면 누릴수 있지 않을까 생각이 들었습니다.

 

 

7. System.out.print() -> BufferedWriter.write()

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());

st = new StringTokenizer(in.readLine());
int[] A = new int[N];
for (int i = 0; i < N; i++)
	A[i] = Integer.parseInt(st.nextToken());

st = new StringTokenizer(in.readLine());
int[] B = new int[M];
for (int i = 0; i < M; i++)
	B[i] = Integer.parseInt(st.nextToken());

BOJ11728_2 main = new BOJ11728_2();
main.solution(N, M, A, B);

StringBuilder sb = new StringBuilder();
for (int i = 0; i < N + M; i++) {
	sb.append(main.sorted[i]).append(" ");
}
out.write(sb.toString());
out.close();

 

사실, 최종 배열을 만들지 않고, 그때, 그때 정렬된 배열의 원소를 출력 해주면 더 속도를 줄일수 있을거라 생각했지만, 이는, 정렬된 배열이 반환되는 인터페이스 였다면, 기능 구현의 문제가 될수 있다고 생각하고, 그대로 구현하돼, System.out.println() -> BufferedWriter.write() 로 만, 변경해 주었습니다. 결과는 변경 전과 같았습니다.