24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글

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

24060번: 알고리즘 수업 - 병합 정렬 1 (acmicpc.net)

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

 

진짜 미친문제.... 의사코드 따라해서 겨우한거같은데 또 이걸 제대로 하지도 못함...
이건 아직도 잘 모르겠다...

다른 알고리즘 책에서 병합정렬 배운거 그대로 구현해서 해봤는데 실패하고 아직 구조이해가 부족한듯?

의사코드 따라해도 안돼서 그냥 참고해서 마무리했다.

정말 머리가 못따라가나... ㅜㅜ
--------

hint - 의사코드가 도움되긴 함

--------

실패한 병합정렬

public class Main {
    
    static int[] buff = new int[500000];
    static int count = 0;
    static int searchCount = 0;
    static int setResult = -1;
    
    static void merge_sort(int[] a, int left, int right) { // 그냥병합정렬
        if(left < right) {
            int center = (left + right) / 2;
            int p = 0;
            int i;
            int j = 0;
            int k = left;
            merge_sort(a, left, center);
            merge_sort(a, center + 1, right);
            
            //1)배열의 앞부분(a[left] ~ a[center])을 
            //buff[0] ~ buff[center - left]에 복사합니다.
            //for문이 끝날 때 p의 값은 복사한 요소의 개수 center - left + 1이 됩니다.
            for(i = left; i <= center; i++) {
                buff[p++] = a[i];
            }
            
            // 2)배열의 뒷부분(a[center + 1] ~ a[right])과 
            //buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 b에 저장합니다.
            while(i<=right && j < p) {
                if(buff[j] <= a[i]) {
                    if(count == searchCount) {
                        setResult = buff[j];
                    }
                    System.out.println("현재 수 : " + buff[j]);
                    a[k++] = buff[j++];
                    count++;
                }
                else {
                    if(count == searchCount) {
                        setResult = a[i];
                    }
                    System.out.println("현재 수 : " + a[i]);
                    a[k++] = a[i++];
                    
                    count++;
                }
            }
            
            
            // 3)배열 buff에 남아있는 요소를 배열 a에 복사합니다.
            while(j < p) {
                if(count == searchCount) {
                    setResult = buff[j];
                }
                System.out.println("현재 수 : " + buff[j]);
                a[k++] = buff[j++];
                count++;
            }
            
        }
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));    
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arrayN = Integer.parseInt(st.nextToken());
        
        searchCount = Integer.parseInt(st.nextToken());
        
        int[] array = new int[arrayN];
        
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < arrayN; i++) {
            array[i] = Integer.parseInt(st1.nextToken());
        }
 
        merge_sort( array, 0, arrayN-1); // 이게 진짜 병합정렬
 
        bw.write(Integer.toString(setResult) + " ");
        bw.write(Integer.toString(count));
        
        bw.flush();
        bw.close();
        
    }
}

망했던 반례 :

8 9
1 2 3 4 5 6 7 8

solution

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    
    static int[] buff = new int[500001];
    static int count = 0;
    static int searchCount = 0;
    static int setResult = -1;
 
    
    static void merge_sort(int a[], int p, int r) {
        if(p < r) {
            int q = (p + r) / 2;
            merge_sort(a, p, q);
            merge_sort(a, q + 1, r);
            merge(a, p, q, r);
        }
    }
    
    static void merge(int a[], int p, int q, int r) {
        int i = p;
        int j = q + 1;
        int t = p;
        
        while(i <= q && j <= r) {
            if(a[i] <= a[j]) {
                buff[t++] = a[i++];
            }
            else {
                buff[t++] = a[j++];
            }
        }
        
        while(i <= q) {
            buff[t++] = a[i++];
        }
        while(j <= r) {
            buff[t++] = a[j++];
        }
        
        i = p;
        while(i<= r) {
            a[i] = buff[i++];
            if(++count == searchCount){
                System.out.println(a[i-1]);
                System.exit(0);
            }
        }
    }
    
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));    
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arrayN = Integer.parseInt(st.nextToken());
        
        searchCount = Integer.parseInt(st.nextToken());
        
        int[] array = new int[arrayN];
        
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < arrayN; i++) {
            array[i] = Integer.parseInt(st1.nextToken());
        }
 
        merge_sort( array, 0, arrayN - 1); // 이게 진짜 병합정렬
 
        bw.write(Integer.toString(setResult));
        
        bw.flush();
        bw.close();
        
    }
}

실행시간 - 720ms

 

언젠가 재도전 해보자...