[코딩테스트 합격자 되기(Java)] 문제 51. 정렬이 완료된 두 배열 합치기★

문제

이미 정렬이 완료되어 있는 두배열 arr1, arr2을 받아 병합정렬하는 Solution()함수를 구현하세요.

 

제약조건

 arr1과 arr2는 각각 길이가 1 이상 100, 000 이하 입니다.
• arr1과ar r2는 각각오름차순으로 정렬되어있습니다.

 

 

입출력 예

arr1	arr2	result
[1,2,3]	[4,5,6]	[1,2,3,4,5,6]
[1,3,5]	[2,4,6]	[1,2,3,4,5,6]

---

풀이 및 코드

병합정렬이므로, 이미 정렬 된 arr1과 arr2를 index0부터 값을 비교하여 채워넣으면 된다.

 

import java.io.*;
import java.util.*;

public class Main {
    private static long bfs(int n, int target){
        if(n == target) return 1;
        Queue<long[]> queue = new LinkedList<>();
        queue.add(new long[]{n, 1L});
        long result = -1;
        long[] info;
        while(!queue.isEmpty()){
            info = queue.poll();
            // 다음 연산 결과가 target과 같으면 연산 값 return
            if(info[0] * 2 == target || info[0]*10+1 == target) return info[1]+1;
            // 연산 결과가 target보다 작을 때만 다음 연산 추가
            if(info[0] * 2 < target) queue.add(new long[]{info[0]*2, info[1]+1});
            if(info[0] * 10 + 1 < target) queue.add(new long[]{info[0]*10+1, info[1]+1});

        }
        return result;

    }


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        br.close();
        System.out.print(bfs(input[0], input[1]));
    }
}