728x90
문제
정렬된 배열 두 개가 주어졌을 때
두 배열을 정렬된 상태로 합치는 문제
접근 방식
{2, 3, 5, 9}
{1, 4, 7}
위와 같은 배열이 두 개 주어졌을 때
1, 2, 3, 4, 5, 7, 9
순서대로 정렬해야 한다.
두 개의 배열은 이미 정렬된 상태이니
각 배열의 첫 번째 인덱스들부터 서로 비교하며
작은 순서대로 다른 배열에 추가하거나 출력해주면 된다.
병합 정렬의 개념에 대해서 공부하기 좋은 문제로
이미 정렬된 두 개의 배열이 주어지기 때문에 풀기가 쉬웠다.
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
String[] input1 = br.readLine().split(" ");
String[] input2 = br.readLine().split(" ");
int[] A = new int[n];
int[] B = new int[m];
for (int i = 0; i < n; i++) {
A[i] = Integer.parseInt(input1[i]);
}
for (int i = 0; i < m; i++) {
B[i] = Integer.parseInt(input2[i]);
}
int aIdx = 0;
int bIdx = 0;
for (int i = 0; i < n + m; i++) {
if (aIdx == n) {
sb.append(B[bIdx++]).append(" ");
} else if (bIdx == m) {
sb.append(A[aIdx++]).append(" ");
} else if (A[aIdx] >= B[bIdx]) {
sb.append(B[bIdx++]).append(" ");
} else {
sb.append(A[aIdx++]).append(" ");
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 11729번 : 하노이 탑 이동 순서 (1) | 2023.10.14 |
---|---|
[백준] 1629번 : 곱셈 (1) | 2023.10.13 |
[백준] 10026번 : 적록색약 (0) | 2023.10.11 |
[백준] 1012번 : 유기농 배추 (0) | 2023.10.11 |
[백준] 1697번 : 숨바꼭질 (0) | 2023.10.11 |