실버III
https://www.acmicpc.net/problem/24060
24060번: 알고리즘 수업 - 병합 정렬 1
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
www.acmicpc.net
문제
오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.
크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.
merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
if (p < r) then {
q <- ⌊(p + r) / 2⌋; # q는 p, r의 중간 지점
merge_sort(A, p, q); # 전반부 정렬
merge_sort(A, q + 1, r); # 후반부 정렬
merge(A, p, q, r); # 병합
}
}
# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
i <- p; j <- q + 1; t <- 1;
while (i ≤ q and j ≤ r) {
if (A[i] ≤ A[j])
then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
}
while (i ≤ q) # 왼쪽 배열 부분이 남은 경우
tmp[t++] <- A[i++];
while (j ≤ r) # 오른쪽 배열 부분이 남은 경우
tmp[t++] <- A[j++];
i <- p; t <- 1;
while (i ≤ r) # 결과를 A[p..r]에 저장
A[i++] <- tmp[t++];
}
입력
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.
다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
출력
배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.
접근방법
[4] [5] [1] [3] [2] 배열의 요소를 예시로 설명을 해보자면,
1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
전반부는 p부터 중간지점인 q까지이므로 [4], [5]까지, 후반부는 [1], [3], [2]가 된다.
그럼 재귀로 또 분할한다. 전반부는 [4]와 [5]로 분할되고, 후반부는 [1]과 [3], [2]로 분할된다.
2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
[4], [5]는 그대로, [1] 그대로, [3], [2]는 순서가 바뀌어 정복된다.
따라서, [4] [5] / [1] / [2] [3] 과 같이 정복된다.
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 이 부분리스트들을 결합하여 오름차순 정렬형태로 만든다.
cnt를 전역변수로 두어 결과를 저장할 때마다 횟수를 들려주었고, cnt가 K와 같아지게 되면 그때 저장되는 요소를 result에 저장하였다.
코드
package 재귀;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class SLIVER3_BJ24060 {
/*https://www.acmicpc.net/problem/24060
알고리즘 수업-병합정렬1
*/
static int[] tmp;
static int cnt = 0; //저장횟수
static int K;
static int result = 0;
public static void main(String args[])throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
//N과 K입력
int N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
//배열 A입력
int[] A = new int[N];
tmp = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < N; i++)
A[i] = Integer.parseInt(st.nextToken());
merge_sort(A, 0, (N - 1));
if(cnt < K)
System.out.println(-1);
else
System.out.println(result);
}
public static void merge_sort(int A[], int p, int r) { // A[p..r]을 오름차순 정렬한다.
if (p < r) {
int q = (p + r) / 2; // q는 p, r의 중간 지점
merge_sort(A, p, q); // 전반부 정렬
merge_sort(A, q + 1, r); // 후반부 정렬
merge(A, p, q, r); // 병합
}
}
//A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
//A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
public static void merge(int A[], int p, int q, int r) {
int i = p;
int j = q + 1;
int t = 0;
while (i <= q && j <= r) {
//왼쪽이 오른쪽보다 작으면 왼쪽 요소를 tmp에 저장
if (A[i] <= A[j])
tmp[t++] = A[i++];
// 왼쪽이 오른쪽보다 작으면 오른쪽 요소를 tmp에 저장
else
tmp[t++] = A[j++];
}
while (i <= q) { // 왼쪽 배열 부분이 남은 경우
tmp[t++] = A[i++];
}
while (j <= r) { // 오른쪽 배열 부분이 남은 경우
tmp[t++] = A[j++];
}
i = p;
t = 0;
// 결과를 A[p..r]에 저장
while (i <= r){
A[i] = tmp[t];
//저장 후 저장횟수 증가
cnt++;
//K번째 저장횟수의 A[i]를 result에 저장
if(K == cnt) {
result = A[i];
}
i++;
t++;
}
}
}
NOTE
코드는 완성하였지만 이해가 완벽하게 되지 않아 아래 블로그들을 참고하여 mergeSort에 대한 이해를 하려고 했다.
하지만 완벽하게 이해가 되지 않은 것 같아 위의 설명도 틀린 부분이 있을 수 있고 많이 부족하다.
좀 더 공부를 해야할 필요성을 느꼈다.
https://velog.io/@gogumi4502/Java-%EB%B0%B1%EC%A4%80-24060-%EC%9E%AC%EA%B7%80
[Java] 백준 #24060 (재귀)
출처 : https://www.acmicpc.net/problem/24060오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 서로 다른 양의 정수가 저
velog.io
[Beginner][백준] 24060번 : 알고리즘 수업 - 병합 정렬 1
https://www.acmicpc.net/problem/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN
dongdori.com
'💻 Algorithm > 재귀' 카테고리의 다른 글
[JAVA] 백준 25501 - 재귀의 귀재 (1) | 2023.11.22 |
---|---|
[JAVA] 백준 10870 - 피보나치5 (0) | 2023.11.21 |
[JAVA] 백준 27433 - 팩토리얼2 (2) | 2023.11.20 |