[BOJ] 1377번: 버블 소트

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

1377번: 버블 소트

문제

입력

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

 

출력

정답을 출력한다.

 

난이도

골드 2

 

Try 1

버블 소트라는 제목을 보고 곧이곧대로 버블 정렬 알고리즘을 가져다 쓰고 루프 돈 횟수를 출력했는데 메모리 초과가 떴다.. N이 500,000보다 작거나 같은 자연수라는 조건 때문에 버블 정렬을 사용하면 메모리든 시간이든 초과될 수밖에 없는듯

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int loop = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 수의 개수
        int[] arr = new int[N];

        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(Arrays.toString(arr));

        // input

        bubbleSort(arr);
        // operation

        System.out.println(loop);
        // output : swap이 일어나지 않을 때(정렬이 끝났을 때) 몇 번째 루프인지
    }

    static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void bubbleSort(int[] arr){
        boolean changed = false;
        int len = arr.length;

        for(int i=0; i<len-1; i++){
            changed = false;
            for(int j=0; j<len-1-i; j++){
                if(arr[j] > arr[j+1]) {
                    changed = true;
                    swap(arr, j, j + 1);
                }
            }
            if(changed == false){
                loop = i+1;
                break;
            }
        }
    }
}

 

Try 2

한 시간 정도 고민했는데 해결책이 떠오르지 않아 책을 참고해서 풀었다.. 

 

별도의 클래스를 생성해서 입력단에서 값과 인덱스를 함께 저장했고, 값(value)을 기준으로 sort() 함수를 돌렸다. Arrays.sort()는 시간 복잡도가 O(nlogn)이기 때문에 버블 정렬보다 훨씬 빨리 돌아간다..!

모든 값의 정렬 전 인덱스와 정렬 후 인덱스를 비교해 가장 왼쪽으로 많이 이동한 값을 찾는 방식으로 해결할 수 있었다. 모든 값들은 루프 한 번 당 최대 한 번만 왼쪽으로 이동할 수 있기 때문에 왼쪽으로 이동한 횟수의 최댓값이 곧 루프가 돌아간 횟수가 된다. 값이 모두 정렬된 뒤 반복문이 한 번 더 돌아가는 것을 감안해 출력단에서 1을 더했다.

 

맞는 풀이인 것 같은데 백준에서 메모리 초과가 떠서 다시 시도했다..!

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 수의 개수
        arrIdx[] arr = new arrIdx[N];

        for(int i=0; i<N; i++){
            arr[i] = new arrIdx(sc.nextInt(), i); // value, index i 저장
        }
        // input

        Arrays.sort(arr);

        int max = 0;
        for(int i=0; i<N; i++){
            if(max < arr[i].index - i){
                max = arr[i].index - i;
            }
        }
        // operation

        System.out.println(max + 1);
        // output
    }
}

class arrIdx implements Comparable<arrIdx>{
    // 기존 인덱스와 값을 함께 저장해두기 위한 별도의 클래스 생성
    int value;
    int index;

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

    @Override
    public int compareTo(arrIdx o){
        return this.value - o.value;
    } // sort() 돌렸을 때 value 기준으로 오름차순 정렬하기 위해 compareTo 재정의
}

 

Sol

Scanner를 BufferedReader로 바꿔줬더니 금방 해결됐다. Scanner가 시간만 오래 걸리는 줄 알았는데 메모리도 많이 잡아먹는구나..! 둘의 차이에 대해 다시 한 번 알아둬야 될 것 같다. 그 외의 코드는 Try 2의 코드와 같다.

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine()); // 수의 개수
        arrIdx[] arr = new arrIdx[N];

        for(int i=0; i<N; i++){
            arr[i] = new arrIdx(Integer.parseInt(bf.readLine()), i); // value, index i 저장
        }
        // input

        Arrays.sort(arr);

        int max = 0;
        for(int i=0; i<N; i++){
            if(max < arr[i].index - i){
                max = arr[i].index - i;
            }
        }
        // operation

        System.out.println(max + 1);
        // output
    }
}

class arrIdx implements Comparable<arrIdx>{
    // 기존 인덱스와 값을 함께 저장해두기 위한 별도의 클래스 생성
    int value;
    int index;

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

    @Override
    public int compareTo(arrIdx o){
        return this.value - o.value;
    } // sort() 돌렸을 때 value 기준으로 오름차순 정렬하기 위해 compareTo 재정의
}

 

😯

버블 정렬의 원리를 알아야 하지만 코드에는 버블 정렬의 요소가 조금도 들어가지 않아서 신기했다. 이런 아이디어는 어떻게 떠올리는거지?!! 문제 해결 능력을 키우려면 많이 풀어보는 수밖에 없겠지?,,,

 

참고

Do it! 알고리즘 코딩 테스트 자바 편 105쪽의 아이디어