반응형

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

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

 

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

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

www.acmicpc.net

 

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

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

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

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


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


--------

실패한 병합정렬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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();
        
    }
}
cs

망했던 반례 :

8 9
1 2 3 4 5 6 7 8

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
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();
        
    }
}
cs


실행시간 - 720ms

 

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

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18
1920번 수 찾기 자바로 풀어 본 짧은 글  (0) 2023.01.14
1427번 소트인사이드 자바로 풀어 본 짧은 글  (1) 2023.01.08
백준 2563번 색종이 자바로 풀어 본 짧은 글  (0) 2023.01.05

+ Recent posts

티스토리툴바