[백준 11728] 배열 합치기 - JAVA // le_effort

배열 합치기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1.5 초	256 MB	14994	6631	4302	43.983%

문제

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

입력

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

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

출력

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

예제 입력 1 복사

xxxxxxxxxx
2 2
3 5
2 9

예제 출력 1 복사

xxxxxxxxxx
2 3 5 9

예제 입력 2 복사

xxxxxxxxxx
2 1
4 7
1

예제 출력 2 복사

xxxxxxxxxx
1 4 7

예제 입력 3 복사

xxxxxxxxxx
4 3
2 3 5 9
1 4 7

예제 출력 3 복사

xxxxxxxxxx
1 2 3 4 5 7 9

 

 

풀이

 

주의사항 3종세트

Arrays.sort보다 Collections.sort가 빠르다.

정답을 출력 할 땐 sysout으로 찍으면 시간초과 난다.

StringBuilder에 넣어서 한번에 출력해줘야 한다.

 

 

위 주의사항을 잘 지키고 투포인터 알고리즘을 이용해서 정렬을 해주면 됩니다.

 

사실 말이 정렬이지 이미 정렬된 A와 B를 가지고 현재 인덱싱 포인트로 작은 값을 넣어주면 됩니다.

 

이 때, a 배열과 b배열의 중 하나는 모든 원소가 정답 배열에 들어 갈 수 있지만 다른 하나는 인덱스가 남아 있을 수 있으니 나머지를 넣어줘야 합니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
public class Main {
    static int n,m;
    static ArrayList<Integer>a = new ArrayList<>();
    static ArrayList<Integer>b = new ArrayList<>();
    static ArrayList<Integer>ans = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws  IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        String [] t = br.readLine().split(" ");
        
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        
        t = br.readLine().split(" ");
        
        for(int i=0; i<t.length; i++) {
            a.add(Integer.parseInt(t[i]));
        }
        
        t = br.readLine().split(" ");
        for(int i=0; i<t.length; i++) {
            b.add(Integer.parseInt(t[i]));
        }
        
        
        Collections.sort(a);
        Collections.sort(b);
        
        int a_point=0;
        int b_point = 0;
        int idx = 0;
        while(a_point< a.size() && b_point<b.size()) {
            if(a.get(a_point) > b.get(b_point)) {
                ans.add(b.get(b_point));
                b_point++;
            }
            else {
                ans.add(a.get(a_point));
                a_point++;
            }
        }
        
        
        // a_point가 남아 있을경우 나머지 다 넣어준다
        
        while(a_point < a.size()) {
            ans.add(a.get(a_point++));
        }
        
        while(b_point <b.size()) {
            ans.add(b.get(b_point++));
        }
        
        for(int i=0; i<ans.size(); i++) {
            sb.append(ans.get(i)+" ");
        }
        System.out.println(sb);
        
    }
}
​