백준 24060번 알고리즘 수업 - 병합 정렬 1 자바 Java

백준 10단계 4번 문제 - 24060 알고리즘 수업 - 병합 정렬 1

https://www.acmicpc.net/problem/24060

24060번: 알고리즘 수업 - 병합 정렬 1

 

 

 

---

10. 재귀 (4) 백준 24060번 문제 알고리즘 수업 - 병합 정렬 1

---

문제

---

 

 

 

 

 

---

정답 인정 코드

---

 

https://jih3508.tistory.com/12

이 블로그를 참고했다

 

합병 정렬(병합 정렬)은 처음 보는 개념인 데다가

추가한 지 얼마 되지 않은 문제라서 풀이가 위에 첨부한 링크의 블로그 하나 뿐이라 이해하는 데 애를 먹었다

 

물론 자바로 된 합병 정렬/병합 정렬 자료 자체는 많은 편이지만 문제가 요구하는 사항이 또 있어 순탄치 않았다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
 
public class Main {
    
    static int[] arr, tmp;
    static int count = 0;
    static int result = -1;    //count가 k보다 작으면 -1 출력하기 위해 초기화
    static int K;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        
        arr = new int[N];
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        tmp = new int[N];
        merge_sort(arr, 0, N - 1);    //인덱스 0부터 n-1까지 = 크기가 n인 배열
        System.out.println(result);
        
    }
    
    public static void merge_sort(int[] A, int start, int end) {
        if (count > K) return ;
        if (start < end) {
            int mid = (start + end) / 2;    //정렬 나눌 중앙값
            merge_sort(A, start, mid);        //처음~중앙값 정렬1
            merge_sort(A, mid + 1, end);    //중앙값+1~끝 정렬2
            merge(A, start, mid, end);        //정렬 후 병합
        }
    }
    
    public static void merge(int[] A, int start, int mid, int end) {
        int i = start;    //정렬1 시작 인덱스
        int j = mid + 1;    //정렬2 시작 인덱스
        int t = 0;        //0부터 시작
        
        while (i <= mid && j <= end) {    //정렬1, 2가 각각 인덱스 값 안에서 돌 때
            if(arr[i] <= arr[j]) {    //정렬2의 첫번째값이 크면
                tmp[t] = arr[i];    //저장하는 정렬 tmp에 정렬1값을 넣는다(더 작은 수)
                i++;                //정렬1의 다음 값으로
            }else {                    //정렬1의 첫번째값이 크면
                tmp[t] = arr[j];    //저장하는 정렬 tmp에 정렬2값을 넣는다(더 작은 수)
                j++;                //정렬2의 다음 값으로
            }
            t++;                    //저장하는 정렬 tmp의 인덱스값을 1씩 늘린다(옆자리 반복해서 구하기)
        }
        
        while (i <= mid)     //정렬1 처음부터 끝까지
            tmp[t++] = arr[i++];
 
        while (j <= end)     //정렬2 처음부터 끝까지
            tmp[t++] = arr[j++];
        
 
        i = start;
        t = 0;
        while (i <= end) {    //처음부터 끝까지 정렬 반복
            count++;    //저장할 때마다 1씩 늘어난다
            if (count == K) {    //count가 k와 같다면
                result = tmp[t];    //result값은 k번째에 저장된 값을 불러온다
                break;
            } 
            arr[i++] = tmp[t++];
        }
    }
    
}

 

일단 최대한 주석을 달아놨다

 

 

 

---

직후 백지 복습

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    static int[] arr, tmp;
    static int count = 0;
    static int k;
    static int result = -1;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.valueOf(st.nextToken());
        k = Integer.valueOf(st.nextToken());
        
        arr = new int[n];    //★
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(st.nextToken());
        }
        tmp = new int[n];    //★
        merge_sort(arr, 0, n-1);
        System.out.println(result);
    }
 
    public static void merge_sort(int[] arr, int start, int end) {
        if(count > k) return ;
        if(start < end) {
            int mid = (start+end)/2;
            merge_sort(arr, start, mid);
            merge_sort(arr, mid+1, end);
            merge(arr, start, mid, end);
        }
    }
    
    public static void merge(int[] arr, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;    //★ end → mid+1
        int t = 0;
        
        while(i <= mid && j <= end) {
            if(arr[i] <= arr[j]) {
                tmp[t] = arr[i];
                i++;
            }else {
                tmp[t] = arr[j];
                j++;
            }
            t++;
        }
        
        while(i <= mid) {
            tmp[t++] = arr[i++];    //★ 순서 반대로 함
        }
        
        while(j <= end) {
            tmp[t++] = arr[j++];    //★ 순서 반대로 함
        }
        
        i = start; //★
        t = 0; //★
        while(i <= end) {
            count++;
            if(count == k) {
                result = tmp[t];
                break;
            }
            arr[i++]=tmp[t++];
        }
    }
}
 

 

주석에 ★을 표시한 부분은 뺴먹었거나 잘못 적었던 부분들

확실히 다시 쳐보면서 이해가 되는 부분도 있다

 

 

 

---

더 좋은 코드가 올라오거나, 내가 생각해낸다면 바로 수정해야겠다

내 기준 지금까지 중 제일 어려웠던 것 같다

포기하고 싶었는데 꾹 참고 주석 달았다..