코딩 테스트 [정렬] - 버블 소트 프로그램1

영식이는 다음과 같은 버블 소트 프로그램을 C++로 작성했다

bool change = false;
for(int i = 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;
	}
}

위 코드에서 n은 배열의 크기, a는 수가 들어 있는 배열이다. 수는 배열의 1번 방부터 채운다. 위와 같은 코드를 실행시켰을 때 어떤 값이 출력되는지를 구하는 프로그램을 작성하시오.

---

입력

1번째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수다. 2번째 줄부터 N개의 줄에 A[1]부터 A[N]까지 1개씩 주어진다. A에 들어 있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

정답을 출력한다.

예제 입력
5	// 배열의 크기
10
1
5
2
3

예제 출력
3

---

1단계 - 문제 분석하기

버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제이다. swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬됬음을 의미한다. 이때는 프로세스를 바로 종료해 시간 복잡도를 줄일 수 있다. 하지만 N의 최대 범위가 500,000이므로 버블 정렬을 사용하면 시간을 초과할 수 있다. 안쪽 for문이 몇 번 수행됬는지 구하는 다른 아이디어가 필요하다.

안쪽 for문이 몇 번 수행됬는지 구하는 다른 아이디어

안쪽 루프는 1에서 n-j까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 실행한다. 이는 특정 데이터가 안쪽 루프에서 swap으로 왼쪽으로 이동할 수 있는 거리가 최대 1이라는 뜻이다. 즉 데이터 정렬 전 index와 데이터 정렬 후 index를 비교해 가장 많이 이동한 값을 찾으면 안쪽 for문이 몇 번 수행됬는지 알 수 있다.

2단계 - 손으로 풀어 보기

1 자바에서 기본적으로 제공하는 sort()는 시간복잡도가 O(nlogn)이므로 이를 사용해 정렬한다.

2 각 데이터마다 정렬 전 index값에서 정렬 후 index 값을 빼고 최댓값으 찾는다. 그 후 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 +1한다.

data	1	2	3	5	10
정렬 전 index	1	3	4	2	0
정렬 후 index	0	1	2	3	4
결괏값	0	2	2	-1	-4

2 + 1 = 3

3단계 - sudo코드 작성하기

N(데이터 개수) A(데이터 배열, 단 클래스를 데이터로 담는 배열)

for(N만큼 반복) {
	A 배열 저장
}

A배열 정렬

for(N만큼 반복) {
	A[i]의 정렬 전 index - 정렬 후 index 계산의 최댓값을 찾아 저장하기
}

최댓값 +1 출력

별도 클래스 선언
mData(데이터 표현) {
	index, value
    value 기준 오름차순 정렬 함수 Comparable 구현하기
}

4단계 - 코드 구현하기

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

public class Q16 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        mData[] A = new mData[N];
        for(int i = 0; i < N; i++){
            A[i] = new mData(Integer.parseInt(br.readLine()), i);
        }
        Arrays.sort(A);

        int Max = 0;

        for(int i = 0; i < N; i++){
            if(Max < A[i].index - i){
                Max = A[i].index - i;
            }
        }

        System.out.println(Max + 1);

    }

    static class mData implements Comparable<mData>{
        int value;
        int index;

        public mData(int value, int index){
            super();
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(mData o){
            return this.value - o.value;
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편