[백준/JAVA] 1517번: 버블 소트

🔺 문제

1517번: 버블 소트

스윗 럽 스윗 드림~ 버블버블~

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static long[] A, tmp;
    static long result;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        A = new long[N + 1];
        tmp = new long[N + 1];
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        result = 0;
        merge_sort(1, N);   // 병합 정렬
        
        System.out.println(result);
    }
    
    public static void merge_sort(int s, int e) {
        if(e - s < 1)
            return;
       
        int mid = s + (e - s) / 2;
        merge_sort(s, mid);
        merge_sort(mid + 1 , e);
        
        // tmp 배열 저장
        for(int i = s ; i <= e ; i++) {
            tmp[i] = A[i];
        }
        
        // 두 그룹 병합
        int tmpIdx = s; // 현재 복사 위치
        int idx1 = s;
        int idx2 = mid + 1;
        
        while(idx1 <= mid && idx2 <= e) {
            if(tmp[idx1] > tmp[idx2]) { // 뒤쪽 데이터 값이 작은 경우 업데이트
                A[tmpIdx] = tmp[idx2];
                result += idx2 - tmpIdx; // 🔔 업데이트
                tmpIdx++;
                idx2++;
            }
            else {
                A[tmpIdx++] = tmp[idx1++];
            }
        }
        
        // 부분이 남은 경우
        while(idx1 <= mid) {
            A[tmpIdx++] = tmp[idx1++];
        }
        while(idx2 <= e) {
            A[tmpIdx++] = tmp[idx2++];
        }
    }
}

✅ 해결 아이디어
- O(nlogn)의 시간 복잡도로 정렬 수행
- 병합 정렬 : 분할 → 정렬 → 합병. 

 

💥 유의사항

두 그룹 병합하는 로직의 첫 번째 while문 안의 if문에서 tmp[idx1] > tmp[mid]이 먼저 나와야한다....

별 생각 없이 두개 순서 바꿔서 작성해봤었는데 안 그러면 67%에서 자꾸 틀림,,,,

 

사유는 아래와 같음,,

 

---

🔺 다른 풀이들

- 정렬 메소드와 합병 메소드를 따로 두심.

백준 1517번. 버블 소트 (Java)

 

 

- 복습용..

백준 1517번: 버블 소트 [분할정복][재귀] - Java

 

 

 

- 신기방기...

[백준 1517] 버블 소트 (JAVA)

---

💬 느낀 점

병합 정렬,,,,, 마스터하고 말거다...

 

1회독	2회독	3회독	4회독	5회독
V	6/14

 

 

( + 6/14 2회독)

import java.util.*;
import java.io.*;
 
public class Main {
    static long[] A, tmp;
    static long cnt;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        A  = new long[N + 1];
        tmp  = new long[N + 1]; // 임시 저장 배열
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }
        
        cnt = 0;
        merge_sort(1, N);
        System.out.println(cnt);
    }
    
    // 1. 분할
    private static void merge_sort(int s, int e) {
        if(s < e) {
            int mid = s + (e - s) / 2;
            merge_sort(s, mid);
            merge_sort(mid + 1, e);
            merge(s, mid, e);
        }
    }
    
    // 2. 정복
    private static void merge(int s, int m, int e) {
        // 정렬이 필요한 배열을 필요한 만큼 "매번" 복사
        for(int i = s ; i <= e ; i++) {
            tmp[i] = A[i];
        }
        
        // 두 그룹 병합 로직
        int l = s;
        int r = m + 1;
        int idx = s;    // 현재 복사 위치
        
        while(l <= m && r <= e) {
            if(tmp[l] <= tmp[r]) {
                A[idx] = tmp[l];
                l++;
            } else {    // 뒤쪽 데이터 값이 작은 경우 swap 발생했으므로 cnt 업데이트
                A[idx] = tmp[r];
                cnt += (m + 1 - l);     // 🔔 앞쪽 배열의 남은 데이터 개수만큼 더함
                r++;
            }
            idx++;
        }
        
        // 앞쪽 배열에 데이터 남아있는 경우, 배열 끝에서 남은만큼을 돌면서 값 채우기
        // (뒷 부분에 남은 거는 상관 없음)
        while(l <= m) {
            A[idx++] = tmp[l++];
        }
       // while(r <= e) {
       //     A[idx++] = tmp[r++];
       // }
    }
}

두 번째 본다고 좀 알 것 같다..만

혼자서 구현은 못 했다. (분발하자!!!)

 

암튼 이번에 풀면서 느꼈던 점 및 유의사항은 아래와 같다...

 

 

1) 28번째 줄 int mid = s + (e - s) / 2; 를  int mid = (s + e) / 2;로 써도 된다.

 

2) 정렬이 필요한 배열은 "매번" 복사해야 한다.

 

3) 48번째 줄 if(tmp[l] <= tmp[r]) ☞ 등호 빠뜨리면 틀리더라...

 

4) 52-54번째 줄 : 순서를 조심해야 한다. A[idx++] = tmp[r++] 하고 cnt 업데이트 하면 틀린다.

순서가 반드시 1) 현재 idx와 r을 이용해 cnt 세기 → 2) 갯수 ++ 어야 한다.

 

5) 53번째 줄 : cnt += (m + 1 - l);를 cnt += r - idx;  로 해도 된다. 원소가 앞으로 이동한 거리만큼 result에 더하는 것..

 

 

---

(참고)

 

✔ 병합 정렬 문제

[백준/JAVA] 24060번: 알고리즘 수업 - 병합 정렬 1

[백준/JAVA] 2751번: 수 정렬하기 2