[Algorithm] 백준 1377번_버블_소트(Java)

🔗 1377번 버블 소트

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

1377번: 버블 소트

 

문제

버블 소트 알고리즘을 다음과 같이 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이다.

 

출력

정답을 출력한다.

 

💡접근 방법 및 풀이

처음에는 무조건 저 코드대로 따라하면 될 것 같기에.. 똑같이 만들고 돌려봤더니 역시나 시간초과.

범위를 다시 보니 N 범위가 500,000까지 이므로 다른 방법을 생각해야한다.

Arrarys.sort() 함수를 쓰면 시간 초과 문제는 해결 될 것 같은데.. 어떻게 정답을 구해야할지 고민하였다.

내가 한 풀이는 다음과 같다.

1. Number 클래스를 만들어 숫자와, 인덱스를 넣는다.
2. Number 배열을 숫자를 기준으로 정렬한다.
3. 0 ~ N-1까지 반복하면서 정렬 후 인덱스와 저장된 인덱스 값의 최대값을 찾는다.
4. 출력

 

💻 코드

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


public class Main {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        Number[] arr = new Number[N];
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            arr[i] = new Number(num, i);
        }

        // 정렬
        Arrays.sort(arr);

        int result = 0;
        for (int i = 0; i < N; i++) {
            result = Math.max(result, arr[i].index - i);
        }
        sb.append(result + 1);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static class Number implements Comparable<Number> {
        int num;
        int index;
        public Number(int num, int index) {
            this.num = num;
            this.index = index;
        }

        @Override
        public int compareTo(Number o) {
            return this.num - o.num;
        }
    }
}