[백준] 1377번 - 버블 소트 (Java)(△)

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

1377번: 버블 소트

<풀이 #1>

 

<구현 #1>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.lang.Comparable;

public class Main {
    static int N;
    static int A[];


    void swap(int a, int b) {
        int tmp = a;
        A[a] = A[b];
        A[b] = A[tmp];
    }
	void Solve() {
        boolean 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]);
                    swap(j, j+1);
                }
            }
            if (changed == false) {
                //cout << i << '\n';
                System.out.println(i);
                break;
            }
        }
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        N = Integer.parseInt(br.readLine());
        A = new int[N+1];
        //StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}

 

<Hint>

1. 버블소트는 앞에서부터 탐색해서 가장 큰 수를 제일 뒤로 보내는 정렬 방법이다.

2. 가장 뒤가 정해지면 그 다음 루프는 그 바로 앞까지만 돌린다.

3. 위 방법 그대로 사용하면 N < 500,000이기 때문에 O(N^2) 알고리즘으로는 타임아웃이 발생한다.

4. 안쪽 루프가 몇번 돌았는지 확인하는 문제이다.

  - 각 인덱스가 정렬 후에 몇 칸 이동했는지를 확인해서 가장 많이 이동한 수에다가 +1을 하면 구할 수 있다.

  - +1을 하는 이유는 정렬 후에 i++ 한 값이 출력되기 때문이다.

5. class Data { int value, int index }를 만들어서 원래 위치의 인덱스 정보를 가지고 가도록 한다.

6. Arrays.sort()를 한 후에 달라진 인덱스 위치의 차이를 구한 후 가장 큰 수를 출력하면 된다.

 

 

<구현>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.lang.Comparable;

public class Main {
    static int N;
    static Data A[];

    class Data implements Comparable<Data> {
        int index;
        int value;
        Data (int i, int v) {
            this.index = i;
            this.value = v;
        }
        @Override
        public int compareTo(Data o) {
            return this.value - o.value;
        }
    }

	void Solve() {
        // 오름차순 정렬 : O(nlogn)
        Arrays.sort(A);

        // 변경된 인덱스 중 가장 큰 값 추출
        int max = 0;
        for (int i=0; i<N; i++) {
            int gap = A[i].index - i;
            max = Math.max(max, gap);
        }
        System.out.println(max+1);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        N = Integer.parseInt(br.readLine());
        A = new Data[N];
        //StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            int v = Integer.parseInt(br.readLine());
            A[i] = new Data(i, v);
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}