백준 1377 - 버블 소트

YongHyun·2023년 4월 5일

백준, 프로그래머스 - 코딩테스트

목록 보기

16/43

문제

시간 제한 2초

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

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

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

입력

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

출력

정답을 출력한다.

문제풀이

처음 문제를 봤을 때는 지문을 이해하지 못해서 시간이 오래 걸렸다. swap(A[j], A[j + 1]) 이 일어나지 않는 횟수를 구하는걸로 착각하고 하루동안 문제를 풀지 못하였는데
결국 swap한 갯수 + 1(swap이 일어나지 않는 경우) 를 구하는 것이었다.

하지만 N의 최댓값은 500,000 이고 위와 같은 c++ 코드를 바로 적용시키면 바로 시간 초과가 나올 것이다.

버블 정렬은 $N^2$ 의 시간 복잡도를 가지고 있기 때문에 이 문제에서는 적합하지 않고 정렬을 이용하면 문제가 해결된다고 한다.

왜냐하면 sort() 함수를 이용한 시간 복잡도는 $O(nlogn)$ 이기 때문이다.

예제 입력 1

5
10
1
5
2
3

먼저 5개의 수인 {10, 1, 5, 2, 3}을 입력받는다.

인덱스 상태 {0, 1, 2, 3, 4}

그리고 인덱스를 0 부터 시작해서 4 까지 하나 하나 비교하여서 큰 수를 후 순위로 놓는다. {1, 5, 2, 3, 10}

1번째 루프
인덱스 상태 {1, 2, 3, 4, 0}

10은 현재 정렬된 상태이기 때문에 10을 제외한 수를 정렬 한다. {1, 2, 3, 5, 10}

2번째 루프
인덱스 상태 {1, 3, 4, 2, 0}

현재 배열의 상태는 {1, 2, 3, 5, 10} 이기 때문에 정렬이 이미 완료된 상태이다.

3번째 루프
이미 정렬된 상태
인덱스 상태 {1, 3, 4, 2, 0}

이렇게 해서 정답은 총 3번에 루프를 돌았기 때문에 3이 출력된다.

이때 코드에 적용시킬 때 이중 for문을 쓰는 것은 시간 초과가 나오기 때문에 다른 방법을 찾아야 하는데

그 방법은
정렬 전 index - 정렬 후 index 의 최댓값을 찾고 +1 을 하는 것이다.

무슨 소리인가 하면

위와 같이 정렬 전에는 데이터 값은 {10, 1, 5, 2, 3}

정렬 후에는 데이터 값이 {1, 2, 3, 5, 10} 으로 정렬된다.

그러면 정렬 전 10은 정렬 후에는 4만큼 오른쪽으로 이동하게 된것이고 (-4)

정렬 전 1은 정렬 후에는 1만큼 왼쪽으로 (+1)

정렬 전 5는 정렬 후에는 1만큼 오른쪽으로 (-1)

정렬 전 2는 정렬 후에는 2만큼 오른쪽으로 (+2)

정렬 전 3은 정렬 후에는 2만큼 오른쪽으로 이동 (+2)

그러면 결국에는 오른쪽으로 1번 이동한 횟수가 루프를 1번 돌때와 같은 것으로 판단할 수 있다.

그래서 최댓값인 2와 정렬이 모두 끝난 상태 1을 더해주면 결과는 3이 출력된다.

이를 코드에 적용해보면 다음과 같다.

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

public class 버블소트 {

    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(i, Integer.parseInt(br.readLine()));
        }

        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 index;
        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;
        }
    }
}