[자바] 백준 1377 - 버블 소트 (java)

목차

문제 : boj1377

 

 

필요 알고리즘

• 애드혹 (ad-hoc)
  
  • 뭔가 알고리즘이 필요한건 아니고, 이 문제만의 규칙(아이디어)을 찾아 해결하는 애드혹 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  거의 3~4개월만에 문제를 풀어봤다! 역시 알고리즘이 재밌긴하다.
결국 N과 배열이 주어졌을 때, 버블소트가 총 몇 번 돌아야 해결되냐? 를 묻는 문제이다. 풀이를 말로하면 엄청 쉽긴한데, 아무래도 아이디어 문제다보니 티어가 높은 것 같다.

 

  애드혹 문제이니 풀이를 그대로 쓰면 재미없을 것 같으니, 강력한 힌트만 써보겠다. "버블소트의 경우 소트 1회당 좌측(배열에서 인덱스가 낮은쪽)으로는 최대 1번 이동 가능하다." 이게 생각났다면 풀 수 있다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;

import static java.util.Arrays.sort;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = i;
            arr[i][1] = Integer.parseInt(br.readLine());
        }
        sort(arr, Comparator.comparingInt(o -> o[1]));
        int ans = 0, i = 0;
        for (int[] cur : arr) ans = Math.max(ans, cur[0]-i++);
        System.out.println(ans+1);
    }
}