[BOJ][1377] 버블 소트

1. 문제 링크

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

2. 사용 알고리즘

정렬

3. 풀이

버블 소트를 이용한 정렬 시 몇 단계만에 정렬이 완료되는지 구하는 문제

최초 상태를 1단계로 보기 때문에 출력하는 답은 실제 정렬 단계 + 1

아래 그림과 같이 한 단계 진행할 때마다 뒤로 이동하는 수의 칸의 수는 제한이 없지만, 앞으로는 한 칸 씩만 이동 가능

따라서 정답은 정렬 후 앞으로 가장 많이 이동한 칸의 수 + 1

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/1377.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> v(500003);

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> v[i].first;
        v[i].second = i;
    }
    sort(v.begin(), v.begin() + n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (v[i].second - i > ans) {
            ans = v[i].second - i;
        }
    }
    cout << ans + 1 << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/1377.java

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 br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Number[] number = new Number[n];
        for(int i = 0; i < n; ++i) {
            int num = Integer.parseInt(br.readLine());
            number[i] = new Number(num, i);
        }
        Arrays.sort(number);
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            if(number[i].index - i > ans) {
                ans = number[i].index - i;
            }
        }
        System.out.println(ans + 1);
    }

    static class Number implements Comparable<Number> {
        int num;
        int index;

        Number(int num, int index) {
            this.num = num;
            this.index = index;
        }

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