-
[3_1][Java] 두 배열 합치기Algorithm/Others 2022. 2. 16. 22:26
문제 유형 : Sort, Two Pointers Algorithm
문제
오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.입력
첫 번째 줄에 첫 번째 배열의 크기 N(1 <= N <= 100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1 <=M <= 100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.출력
오름차순으로 정렬된 배열을 출력합니다.예시 입력1
3
1 3 5
5
2 3 6 7 9
출력
1 2 3 3 4 5 6 7 9나의 풀이
첫 번째 풀이는 정렬을 이용한 간단한 풀이입니다. 데이터 갯수가 N + M <= 200 이므로 크지 않기에 배열에 넣어 시간 복잡도 O(NlogN)인 Arrays.sort()를 해주면 됩니다. 다만, Arrays.sort()는 DualPivotQuicksort로 구현되어 있기에 최악의 경우 O(N^2)이 될 수 있지만 데이터 갯수가 크지 않기 때문에 괜찮습니다. 안정적인 O(NlogN)을 쓰고 싶으시면 TimSort로 구현된 Collections.sort()를 쓰시면 됩니다. :)
두 번째 풀이는 투 포인터를 이용한 풀이입니다. 각 tp1배열과 tp2배열의 시작 인덱스를 s = 0, e = 0으로 세팅해 줍니다. 그 다음 로직은 다음과 같습니다.
두 값을 비교 후, 만일 작거나 같으면 그 배열의 인덱스를 하나 올려줍니다. 만일, 두 배열 중 하나라도 배열의 인덱스를 벗어나면 끝낸 후, 넣어주지 않은 배열 나머지를 다 list에 넣어주고 출력을 해주면 됩니다. :)
* Java Code
package kosta.mission3; import java.io.*; import java.util.*; public class Solution3_1 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int n, m; static int[] arr, answerArr, tp1, tp2; static List<Integer> list = new ArrayList<>(); public static void main(String[] args) throws IOException { //1. Sort Solution [Two Pointers를 위해 입력 같이 처리] arr = new int[200]; n = Integer.parseInt(br.readLine()); tp1 = new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { String token = st.nextToken(); arr[i] = Integer.parseInt(token); tp1[i] = Integer.parseInt(token); } m = Integer.parseInt(br.readLine()); tp2 = new int[m]; st = new StringTokenizer(br.readLine()); for (int i = n; i < n + m; i++) arr[i] = Integer.parseInt(st.nextToken()); for (int i = 0; i < m; i++) tp2[i] = arr[n + i]; answerArr = new int[n + m]; for (int i = 0; i < n + m; i++) answerArr[i] = arr[i]; Arrays.sort(answerArr); for (int i = 0; i < n + m; i++) System.out.print(answerArr[i] + " "); System.out.println(); //2. Two Pointers Solution int s = 0, e = 0; while (s != n && e != m) { if (tp1[s] < tp2[e]) list.add(tp1[s++]); else if (tp1[s] > tp2[e]) list.add(tp2[e++]); else { list.add(tp1[s++]); list.add(tp2[e++]); } } if (s != n) for (int i = s; i < n; i++) list.add(tp1[i]); else if (e != m) for (int i = e; i < m; i++) list.add(tp2[i]); for (Integer value : list) System.out.print(value + " "); } }