❗️ 해당 솔루션은 Java의 Comparale과 같은 인터페이스, 기본문법 그리고 버블정렬에 대해 알고 있다고 가정하고 작성한 문서이다.

🔍 Problem

백준 1377 버블소트

---

📃 Input&Output

---

🌁 문제 배경

가. 문제 설명
버블정렬의 내부 루프 순서 중에서, 더 이상 정렬이 필요없는 부분의 루프 순서를 구하는 문제이다.

나. 접근 방법

1. Data 클래스를 Comparable 인터페이스 구현을 사용하여 비교 가능한 객체를 만든다.

2. 한 내부루프에서 오름차순 기준, 왼쪽으로 한번밖이 이동할 수 없다.

3. 왼쪽으로 가장 많이 이동한 횟수를 찾으면, 내부 루프의 실행 횟수를 알 수 있다.

   [예시]
   10 1 5 2 3

   위의 경우, 1 2 3 4 10 이고 2와 3이 왼쪽으로 2번이동한 것이 가장 많이 이동한 횟수이다. 이것은 1 2 3 4 10이 되는 경우이고 이때 내부루프의 i는 3이다.

다. 문제 유형
버블정렬, 단순구현

---

📒 수도 코드

가. Compareable한 Data 클래스 구현

class Data implements Comparable<Data>{
	public int idx;
    public int val;
    ...

나. 정렬 후, 왼쪽으로 가장 많이 이동한 횟수 탐색 후 +1하여 출력

---

💻 Code

import java.io.*;
import java.util.*;

public class P16 {

    static class Data implements Comparable<Data>{
        public int idx;
        public int val;

        Data(int idx, int val){
            this.idx=idx;
            this.val =val;
        }

        @Override
        public int compareTo(Data d){
            return this.val-d.val;
        }


    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;



        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        Data[] arr = new Data[N];

        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int val =  Integer.parseInt(st.nextToken());
            arr[i] = new Data(i,val);
        }

        Arrays.sort(arr);
        int max=0;

        for (int i=0; i<N; i++){
            int gap = arr[i].idx-i;             // 수정 필요

            if(max<gap){
                max=gap;
            }
        }




        bw.write(max+1+"");
        bw.flush();
        bw.close();
    }
}

---

🎸 기타

Note

🤔 고찰

Comparable한 객체를 사용할 줄 알면 편하다.