1. 문제 설명 📌

문제 링크

예시로 나온 C++ 코드를 눈으로만 읽어서는 이해가 어렵다. 따라서 N과 A[] 배열에 각각 값을 넣어보며 생각해보길 바란다. 코드의 주요 골자는, 반복 Loop 중에서 최초로 어떠한 수도 SWAP이 일어나지 않는 Loop는 몇 번째냐? 를 구하는 것이다.

2. 접근 방식 🗃️

KEY WORD: Bubble Sort

버블 정렬 자체는 사용하지 못한다. 왜냐하면 입력 데이터의 최대 개수가 500,000 인데, O(N^2)인 버블 정렬을 이용하면 10^9를 넘겨 시간초과가 나기 때문이다. 해당 문제는 Bubble Sort 자체가 아니라, Bubble sort이 작동하는 방식에 대한 정확한 이해를 필요로 한다.

다음과 같은 배열이 주어졌을 때, 첫 번째 Loop를 돌며 버블 소트를 진행한다고 해보자. 그 결과는 10이 최우단으로 자리를 이동했을 것이고, 나머지 값들은 모두 한 칸씩 왼쪽으로 이동했을 것이다.

다음 2 번째 Loop에서는 5가 10의 왼쪽에 위치할 것이고, 2와 3이 왼쪽으로 이동했을 것이다.

이후 3번째 Loop에서는 어떠한 SWAP도 일어나지 않아. 답은 3이 된다.

예시에서 살펴보았다시피, SWAP이 일어난 LOOP에서는 최소 하나의 값이 왼쪽으로 움직인다. 따라서 원소들 중 가장 많이 왼쪽으로 움직인 횟수가 곧 SWAP이 일어난 LOOP의 최종 개수가 될 것이고, 여기서 +1을 더한 것이 최초로 LOOP가 일어나지 않은 LOOP의 번호가 될 것이다. 따라서 풀이를 큰 흐름에 따라 적어보면,

입력 받은 원소들의 최초 INDEX를 적어둔다.
JAVA 내부 정렬 활용 (시간복잡도 O(nlogn))하여 값을 정렬한다.
정렬 후 index - 최초 index == 왼쪽으로 이동한 횟수 임으로 이것의 최대값을 구한다.
해당 최대값 + 1 을 출력한다.

다음은 해당 접근 방식에 대하여 생길 수 있는 의문점과 그에 대한 나의 생각을 적겠다.

(1) 왼쪽 이동 횟수가 중첩된다는 것을 어떻게 확신하냐? 🤔

해당 풀이는 왼쪽 이동 횟수 중 최대값 == SWAP LOOP의 개수라고 가정하고 문제를 풀고 있다. 하지만 '만약 10개의 수에 대해서, Loop 1에서는 1-3의 index에서만 swap이 일어나고, Loop 2에서는 7-9에서만 SWAP이 일어나는 것과 부분적인 이동이 가능하지 않는가?' 하는 의문이 들 수 있다.

하지만 이는 불가능하다. 왜냐하면, 만약 배열의 원소 중 부분적으로 SWAP이 필요하다고 하더라도 해당 SWAP은 동시에 일어나기 때문이다. 예시를 들어보겠다.

[5, 4, 3, 2, 1, 10, 9, 8, 7, 6] 이렇게 있다고 하자. 해당 배열은 5가 배열의 중앙에 오는 SWAP과 10이 배열 끝으로 가는 SWAP이 동시에 일어난다.

위 예시와 같이 특정 부분 내에서의 이동은 항상 동시에 일어나는 것이 보장됨으로, 최대 중첩이 곧 SWAP LOOP의 개수임을 보장할 수 있다.

3. 코드 소개 🔎

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;


public class Main {
    /*
    * 1377 버블 소트
    * (1) 모든 원소의 원래 index를 저장
    * (2) 모든 원소의 정렬 후 index를 구한다.
    * (3) (1) - (2) 중 최대값을 구한다.
    * (4) 최대값 + 1을 출력한다.
    * */
    public static void main(String[] args) throws IOException {
        int answer = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Num [] nums = new Num[N];
        for (int i = 0; i < N; i++) {
            nums[i] = new Num(i, Integer.parseInt(br.readLine()));
        }
        Arrays.sort(nums, Comparator.comparingInt(o -> o.v));
        for (int i = 0; i < N; i++) {
            if(i < nums[i].i) answer = Math.max(answer, nums[i].i - i);
        }
        System.out.println(answer+1);
    }
}

class Num {
    int i;
    int v;

    public Num(int i, int v){
        this.i = i;
        this.v = v;
    }
}

4. 배운 것 🎯

흑... 두 번째 풀이였는데, 스스로 풀지 못했다. 나는 생각의 방향을 오른쪽으로 이동한 값의 개수를 세면 된다고 생각했다. 왜냐하면 SWAP이 일어났다면 최소 하나의 값이 오른쪽으로 이동하기 때문이다. 하지만 이것은 두가지 이유에서 답이 될 수 없다.

(1) 위 예시 처럼 부분적인 이동이 동시에 일어날 때, 이러면 Loop는 하나였는데, 움직인 수는 2개라 계산이 안된다.
(2) 오른쪽으로 이동한 값은 다음 Loop에서 밀려날 수 있음.
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 을 예시로 보면 SWAP이 일어난 LOOP는 총 10개 이지만, 내 잘못된 풀이로 계산하면 6번이 나온다. 왜냐하면 5~2부분이 오른쪽으로 이동했으나, 배열의 최좌단에서 시작해서 최초 index 위치와 비교하면 오른쪽으로 이동한 것이 아니게 되기 때문이다.