BOJ : 11728

1. 문제

 

2. 문제 설명 및 알고리즘 설계

 

- 정렬이 되어있는 배열이므로 배열을 따로 정렬할 필요가 없음

- 배열들의 첫번째 인덱스를 지정할 변수 2개를 지정한다.

- 첫번째 인덱스들부터 확인한다

         규칙 1. 같을 경우 둘 다 넣고 인덱스 둘다 ++
         규칙 2. 작은 값을 넣고 넣은 배열 인덱스 ++

         규칙 3. 한쪽이 다 돌게 되면 다른 쪽 다넣고 ++ 반복

 

3. 코드

package week10;

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

public class Q11728_boj {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());


        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int fir[] = new int[N];
        int sec[] = new int[M];

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

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

        int first = 0;
        int second = 0;

        while(first<N && second<M){
            if(fir[first] == sec[second]){
                sb.append(fir[first] + " ");
                first++;
                sb.append(sec[second] + " ");
                second++;
            }else if(fir[first]>sec[second]){
                sb.append(sec[second] + " ");
                second++;
            }else {
                sb.append(fir[first] + " ");
                first++;
            }
        }

        if(second == M){
            for(int i=first;i<N;i++){
                sb.append(fir[i] + " ");
            }
        }
        if(first == N){
            for(int i=second;i<M;i++){
                sb.append(sec[i]+" ");
            }
        }
        System.out.println(sb);
    }
}

 

4. 시간 복잡도

O(N)

 

5. 결과