[알고리즘] 1377번

오늘 풀어볼 문제는 백준 1377번 문제 "버블 소트" 이다.

이 문제는 골드2 문제이고 버블 정렬 문제이다.

문제

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이다.

출력

정답을 출력한다.

📌첫 번째 도전📌
단순하게 주어진 문제에서 작성한 코드를 자바 코드로 옮겨서 실행해 보았다.
역시 골드 문제답게 시간 초과가 발생했다.

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        arr = new int[N+1];

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }

        boolean change = false;
        for(int i=1; i<=N; i++) {
            change = false;
            for(int j=i; j<=N-i; j++) {
                if(arr[j] > arr[j+1]) {
                    change = true;
                    swap(j, j+1);
                }
            }

            if(change == false) {
                System.out.println(i);
                break;
            }
        }
    }

    private static void swap(int a, int b) {
        int tmp = arr[b];
        arr[b] = arr[a];
        arr[a] = tmp;
    }
}

*📌두 번째 도전📌
버블 정렬을 굳이 만들어서 정렬을 해줄 필요 없이 인덱스 값을 비교하면 얼마나 버블 정렬이 일어나는지 알 수 있다.

예를 들어 아래를 보자.

value : 1 2 3 5 10
정렬 전 index : 1 3 4 2 0
정렬 후 index : 0 1 2 3 4
정렬 전 - 정렬 후 : 1 2 2 -1 -4

위와 같은 도표를 만들어서 정렬 전 - 정렬 후 값 중 가장 큰 값에 1을 더하면 버블 정렬 횟수가 나온다.

위 표는 2+1 = 3 이 정답인 것이다.

public class Main {
    static data[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        arr = new data[N];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = new data(Integer.parseInt(st.nextToken()), i);
        }
        Arrays.sort(arr);
        int max = 0;

        for(int i=1; i<N; i++) {
            if(max < arr[i].index - i) {
                max = arr[i].index - i;
            }
        }
        System.out.println(max+1);
    }
}
class data implements Comparable<data> {
    int value;
    int index;

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

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

그런데 틀렸다는 결과가 나왔다.. 왜지?? 코드에 실수가 있었나 보다.

*📌세 번째 도전📌
마지막 max 값을 구하는 for문에서 i 값을 1부터 시작해서 틀린 것 같다. 다시 수정하여 코드를 돌려보았다.

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

        int N = Integer.parseInt(st.nextToken());
        data[] arr = new data[N];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = new data(Integer.parseInt(st.nextToken()), i);
        }
        Arrays.sort(arr);
        int max = 0;

        for(int i=0; i<N; i++) {
            if(max < arr[i].index - i) {
                max = arr[i].index - i;
            }
        }
        System.out.println(max+1);
    }
}
class data implements Comparable<data> {
    int value;
    int index;

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

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

정답이다!!

[문제 출처] https://www.acmicpc.net/problem/1377