[BOJ] 1377. 버블 소트

[작성일]

• 2022-03-13

[분류]

• 정렬
  
  
  

[문제링크]

• https://www.acmicpc.net/problem/1377
  
  
  

[요구사항]

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

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

[풀이]

버블소트의 원리를 잘 이해하는 것이 중요한 문제이다.

문제의 예시를 통해서 버블 소트의 원리를 자세히 살펴보자.

(1번째 시도)
10 1 5 2 3 (초기상태)
1 10 5 2 3
1 5 10 2 3
1 5 2 10 3
1 5 2 3 10

(2번째 시도)
1 5 2 3 10 (초기상태)
1 2 5 3 10
1 2 3 5 10

1번째 시도에서 각각 이동 횟수를 살펴보면
10 -> -4
1 -> +1
2 -> +1
5 -> +1
3 -> +1
이다.

2번째 시도에서 이전 값에 더해서 살펴보면
10 -> -4
1 -> +1
2 -> +2
3 -> +2
5 -> -1
이다.

즉, 정답은 3이된다.
왜?
위의 버블소트 코드에서는 더 이상 소팅이 필요 없을 경우 index를 출력한다.
살펴보면, 가장 많이 이동한 index의 횟수가 곧 몇번 시도했는지를 의미한다.
그런데 가장 많이 이동한 10은 왜 안될까?
음수 쪽으로는 한 타임에 한 칸씩 이동하는 것이 아니라 여러번 이동가능하다.
1번째 시도에서(1번의 시도만에) 10은 무려 4칸이나 뒤로 이동했기 때문에 횟수와는 관련없다.
반면, 2와 3은 한번의 시도에 한번씩만 이동했기 때문에 둘 다 고려대상이 되는데 숫자가 더 큰 3이 더 나중에 이동하기 때문에 답은 3이다.

[코드]

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


class Main {
    static Node[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new Node[N];

        for (int i = 0; i < N; i++) {
            arr[i] = new Node(Integer.parseInt(br.readLine()), i);
        }

        Arrays.sort(arr, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return Integer.compare(o1.val, o2.val);
            }
        });

        for (int i = 0; i < N; i++) {
            // 원래 위치에서 소팅 후 이동 한 위치까지의 차이를 구한다.
            arr[i].gap -= i;
        }

        int max = 0;
        for(int i = 0; i < N; i++) {
            // 자리 이동 gap이 가장 크고 양수이며, 같을 경우에는 더 뒤에있는 index를 정답으로 한다.
            max = Math.max(max, arr[i].gap);
        }
        System.out.println(max + 1);
    }
}

class Node {
    int val;
    int gap;

    public Node(int val, int gap) {
        this.val = val;
        this.gap = gap;
    }
}