[백준/JAVA] 1377번: 버블 소트

🔺 문제

1377번: 버블 소트

 

🔺 코드

import java.util.*;
import java.io.*;
 
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());
 
        mData[] arr = new mData[N];
        for(int i = 0 ; i < N ; i++) {
            arr[i] = new mData(Integer.parseInt(br.readLine()), i);
        }
        
        Arrays.sort(arr);   // Arrays.sort의 시간 복잡도 : O(nlogn)
 
        int max = 0;
        for(int i = 0 ; i < N ; i++) {
            if(max < arr[i].idx - i)  // 정렬 전 idx - 정렬 후 idx
                max = arr[i].idx - i;
        }
 
        System.out.println(max + 1);
    }
}
 
class mData implements Comparable<mData> {
    int val;
    int idx;
 
    public mData(int val, int idx) {
        super();
        this.val = val;
        this.idx = idx;
    }
 
    @Override
    public int compareTo(mData o) { // val 기준 오름차순 정렬
        return this.val - o.val;    // 본인 - 입력 받은 값
        
        // 자기자신의 val이 o의 val보다 크다면 양수
//        if(this.val > o.val) {
//            return 1;
//        }
        // 자기 자신의 val과 o의 val가 같다면 0
//        else if(this.val == o.val) {
//            return 0;
//        }
        // 자기 자신의 val이 o의 age보다 작다면 음수
//        else {
//            return -1;
//        }        
    }
}

 

✅ 해결 아이디어
- swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제.
→  안쪽 for문이 몇 번 수행됐는지 계산
→ 정렬 전 idx와 정렬 후 idx를 비교해 왼쪽으로 가장 많이 이동한 값 찾기!

- +1 하는 이유 : swap이 일어나지 않은 반복문이 한 번 더 실행되는 것 감안
- Comparable 인터페이스 구현 이유 : 같은 타입의 인스턴스를 서로 비교해야 해서 (자기 자신 vs 매개 변수 객체)

 

💥 유의사항

• N의 최대 범위가 500,000이므로 버블 정렬로 풀었다간 시간 초과가 뜰 것이다..

• 스택에 수열의 값이 아닌, 인덱스를 저장!

 

---

🔺 다른 풀이들

- mData 클래스 객체 만들어 비교하는 대신, 2차원 배열로 받으셨다. (행 : 값, 열 : 인덱스)

로그인

 

- 여기도 풀이 조곰 다르다.

로그인

---

💬 느낀 점

이번 문제 덕분에 Comparable 인터페이스 왜, 어떻게 쓰는지까지 검색해봤다.

 

.

.

 

자바 [JAVA] - Comparable 과 Comparator의 이해

Comparable 인터페이스 특징

- "자기 자신"과 매개 변수 비교

- compareTo() 를 반드시 구현해야 함. - 자기 자신과 비교하므로 인자는 하나

 

.

.

 

 

그리고 compareTo에서 객체를 비교했을 때,

왜 양수일 때는 두 원소 위치를 교환하고,

음수일 때는 두 원소 위치를 교환 안 하는지도 알았다.

default가 오름차순이라서 그랬던 것임!

 

(가정 : 선행 원소 < 후행 원소)

 

.

.

 

이해하고 나면 재밌다 참...

내가 아이디어를 못 생각하고.. 못 풀어서 문제지만ㅋㅋㅋㅋ

1회독	2회독	3회독	4회독	5회독
V	6/13

---

(참고)

✔ 복습용

백준 1377 버블 소트 Java

[BOJ] 백준 1377번 : 버블 소트 (JAVA)

 

 

✔ Comparable 인터페이스

코딩교육 티씨피스쿨