[정렬] 백준 1517번

문제

버블정렬에 관한 이야기 진행
- 인접해 있는 두 수를 swap하며 정렬 진행
- (배열 크기 + 배열 제공)
- 버블정렬을 진행할 때, swap하는 횟수를 구하는 프로그램을 작성하시오

시간 제한 : 1초
버블정렬 시간복잡도 : O(N^2)
배열 범위 : 1<= N <= 500,000

 

문제분석

버블정렬로 진행할 시, 시간 초과로 인해 swap을 구하더라도 문제에 제시되어있는 시간을 지킬 수가 없다.
따라서, O(NlogN)을 가진 정렬하는 방식을 채택해야함
(병합 정렬 선택)

• 병합정렬 선택시 주의할점)
  • 병합정렬이 swap되는 횟수를 구하는 것이 아닌, 버블정렬이 swap되는 횟수를 구해야함
  • 인덱스 위치의 변화를 통한 , 버블정렬의 swap 횟수를 구해야함
• 예시
  • 2를 이동시에 5와 6을 뒤로 보내야한다 ( 버블정렬 시 swap되는 항목 )
    • (2,5) , (2,6) 스왑이 일어남
  • 따라서, 그룹2에서 이동한 인덱스 만큼 버블정렬에서는 swap이 일어남 (아이디어)

그룹1			그룹2
1	5	6	2	3	4
(그룹 1 + 그룹 2 정렬)
1	2	3	4	5	6
	(인덱스 +2 이동)	(인덱스 + 2이동)	(인덱스 +  2이동)

 

 

슈도코드

N (정렬 개수)
arr (정렬 배열)
tmp (병합 정렬시 사용되는 배열)
mergeSort (병합정렬)
결과 출력

//병합정렬 코드
병합정렬 (start , end)
start (시작점)
end (끝점)
middle (중간점)

병합정렬 (start, middle);
병합정렬 (middle+1, end);

// end로 지정한 이유는 ( start ~ middle / middle+1 ~end 2개의 그룹으로 나누기 위해)
for( s ~ e ){
    tmp 배열 저장하기
}

index1 = 앞쪽 그룹
index2 = 뒤쪽 그룹
while(index1 <= 중간점 && index2 <= end ){
    뒤쪽데이터값이 더작아 선택될때,
    swap이 일어났다고 가정하고, 현재 남아있는 앞쪽 데이터 개수만큼 결과값을 더함
    }
    반복문 끝난 후 남아있는 데이터 정리
    
}

 

구현하기

• 병합정렬 구현하기
• "result = result + group2_index - sortIndex" 이번 문제의 해결 포인트

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class App {
    
    public static Long result = 0L;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(bf.readLine());

        int[] arr = new int[size];
        int[] tmp = new int[size];

        StringTokenizer st = new StringTokenizer(bf.readLine());
        int i = 0;
        while(st.hasMoreTokens()){
            arr[i++] = Integer.parseInt(st.nextToken());
        }

        mergeSort(arr,tmp,0, size-1);
        System.out.println(result);
    }



    private static void mergeSort(int[] arr,int[] tmp, int startIndex, int endIndex){
        if (startIndex >= endIndex){
            return;
        }

        int middleIndex = startIndex + (endIndex - startIndex)/2;

        mergeSort(arr, tmp, startIndex, middleIndex);
        mergeSort(arr, tmp, middleIndex + 1, endIndex);
        
        for (int i = startIndex; i <= endIndex; i++){
            tmp[i] = arr[i];
        }

        int sortIndex = startIndex;
        int group1_index = startIndex;
        int group2_index = middleIndex+1;
        
        while(group1_index <= middleIndex && group2_index <= endIndex){
            if(tmp[group1_index] > tmp[group2_index]){ // 정렬되지 않은 곳은 2개의 그룹을 섞을때만 (각각의 그룹은 정렬이 되어있다)
                arr[sortIndex] = tmp[group2_index];
                result = result + group2_index - sortIndex;
                sortIndex++;
                group2_index++;
            }else{
                arr[sortIndex] = tmp[group1_index];
                sortIndex++;
                group1_index++;
            }
        }

        while(group1_index <= middleIndex){
            arr[sortIndex] = tmp[group1_index];
            sortIndex++;
            group1_index++;
        }

        while(group2_index <= endIndex){
            arr[sortIndex] = tmp[group2_index];
            sortIndex++;
            group2_index++;
        }
    }

}