[버블정렬] 백준 1377번

문제

bool change = false;
for (int =1; i<= n + 1; i++){
    change = false;
    for(int j = 1; j <= n - i; j++){
        if ( a[j] > a[j+1] ){
            change = true;
            swap(a[j], a[j+1]);
        }
    }
    if(change == false){
        cout << i << '\n';
        break;
    }
}

위 버블 소트를 구현한 c++ 코드의 의도를 구하는 문제
1. 1번째 줄에 N이 주어진다
( 1 <= N <= 500,000)
2. 2번째 줄부터 N개의 줄에 A[1] ~ A[N] 까지 1개씩 주어진다
( 0 <= A[i] <= 1,000,000 )
3. 시간제한 2초

 

문제 분석

최대 500,000개까지 배열의 개수가 정해질 수 있으므로 O(N^2)일 경우 시간초과가 나게 된다 
(버블 정렬은 시간복잡도가 O(N^2)이므로, 최대 개수는 10,000 이다 - 1초에 1억번 연산)

[해결방법]
1. 문제에서는 버블정렬이 이루어지는, 바깥쪽 for문의 횟수이다
2. 버블정렬의 경우, 최대값부터 정해지게된다 ( 최대 횟수는 맨 뒤의 숫자가 가장 작을때의 수이므로 N 이다 )
3. 버블정렬은 오른쪽으로는 안쪽 for문의 따라 움직이게 되고, 왼쪽으로 이동하는 숫자는 인쪽 for문 하나당 +1 위치이다
4. 왼쪽으로 가장 많이 움직인 인덱스 개수 + 1 이 for 문이 진행된 횟수이다.

 

문제 )  N : 5 / Array : 10, 1, 5, 2, 3

• 바깥쪽 for문 : 1
  • 안쪽 for문
    • 1,10,5,2,3
    • 1,5,10,2,3
    • 1,5,2,10,3
    • 1,5,2,3,10 (10은 이제부터 고정)
  • 이동횟수

1	+1칸
2	+1칸
3	+1칸
5	+1칸
10	-4칸

• 바깥쪽 for문 :2
  • 안쪽 for문
    • 1,5,2,3,10
    • 1,2,5,3,10
    • 1,2,3,5,10 (5,10 고정)

1	0칸
2	+1칸
3	+1칸
5	-1칸
10	0칸

• 바깥쪽 for문 :3
  • 안쪽 for문
    • 1,2,3,5,10 (변동 없음 - 버블정렬 종료)

1	0칸
2	0칸
3	0칸
5	0칸
10	0칸

즉, 각각 인덱스가 옮겨진 개수 중에 최대로 옮겨진 개수 + 1 이 바깥쪽 for문의 횟수가 된다
[이동 횟수]
1 : +1칸
2 : +2칸
3:  +2칸
5:  0칸
10 : -4칸

최대가 +2 이므로, for문의 경우 정렬이 끝났더라도 한번 더 순회하므로, 정답 " 3 " 이다.

슈도코드

• 자바의 sort()기능을 이용하여 (시간복잡도 O(NlogN)), 정렬 후 인덱스와 정렬 전 인덱스의 차이를 이용하여 최대로 많이 왼쪽으로 이동한 횟수의 +1을 구하여 답을 구한다

단) 숫자가 왼쪽으로 움직였다가, 오른쪽으로 다시 위치되는 (ex] 5)의 경우 +-되므로 for문 횟수구하는 것에 영향을 끼치지 않는다

(즉 왼쪽(바깥쪽 for문 한번당 왼쪽으로는 한칸밖에 못움직임)으로 최대로 움직인 횟수가 바깥쪽 for문이 돈 횟수가 된다)

N(데이터 개수) A(데이터 배열)
for(N만큼 반복하기){
    A배열 저장
}
A 배열 정렬하기
for(N만큼 반복하기){
    A[i]의 정렬 전 index - 정렬 후 index 계산의 최대값 찾아 저장하기
}
최대값 +1 출력

index와 value 저장 클래스{
    index,value가지며
    value기준 오름차순 정렬함수 comparable 구현하기
}

 

구현하기

• Arrays.sort()의 객체 정렬의 경우 기준을 잡아줘야하므로, Comparable을 implements를 해야한다
  • @Override compareTo()로, 기준을 설정해야함
  • sort()함수에서 compareTo()를 호출하며 정렬을 진행

compareTo(mData o){
    this.value - o.value;
}

(현재객체 기준)
this.value > o.value : 현재 객체가 뒤로감
this.value == o.value : 정렬 순서 유지
this.value < o.value : 현재객체가 앞으로감 

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

public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(bf.readLine());
        
        mData[] arr = new mData[size];
        
        for(int i = 0; i<size; i++){
            arr[i] = new mData(i, Integer.parseInt(bf.readLine()));    
        }

        Arrays.sort(arr);
        int MAX = 0;
        for (int i =0; i< size; i++){
            if (MAX < arr[i].index - i){ // arr[i].index 는 정렬전 index , i 는 현재 인덱스
                MAX = arr[i].index -i;
            }
        }

        System.out.println(MAX +1);
    }

    public static class mData implements Comparable<mData>{
        private int index;
        private int value;
        
        public mData(int index, int value){
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(mData o){
            return this.value - o.value; // 오름차순 정렬
        }
    }
}