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

버블 소트

📑 문제

백준 1377 버블 소트

---

🌱 아이디어

버블소트의 특징을 활용하자!

 

위 문제는 C++ 버블 소트 코드를 제공한다. 전형적인 버블 소트 알고리즘이며 O(N^2)의 시간복잡도를 가진다

입력으로 1 <= N <= 500,000 범위가 입력되기 때문에 시간제한을 아득히 넘는다.

 

즉 , 위 문제는 버블 소트를 구현하는 문제가 아닌 버블 소트의 특징을 이용하는 문제이다. 

 

결국 정렬하는 문제이다 버블 소트의 정렬 특징을 생각해 보자

 

오른쪽 -> 왼쪽으로 숫자가 이동할 때, 한 턴에 연속적으로 다수의 칸을 이동한다.

왼쪽 <- 오른쪽으로 숫자가 이동할 때, 한 턴에 단 한 번만 이동한다.

 

위 특징을 봤을 때, 결국 버블 소트의 실행 횟수는 왼쪽 <- 오른쪽으로 가장 많이 이동하는 숫자에 종속된다.

 

그렇다면 어떻게 구현할까?

 

해당 숫자와  입력된 위치(인덱스)를 저장하고, 한 번에 정렬 후 현재 숫자 위치(인덱스) - 원래 위치(인덱스)의 차를 구한다

그중 가장 큰 차가 바로 버블소트의 정렬 횟수가 된다. 이제 구현해 보자!

 

---

🌱 코드 및 풀이

class를 하나 만들어서 숫자, 인덱스를 저장한다. 정렬의 최적화를 위해 우선순위 큐를 사용했다. 하지만 유의할 점이 있다.

 

우선순위 큐에서 정렬하게 되면 숫자가 같을 때 인덱스 번호의 순서가 정렬되지 않는다.

 

 

인덱스 순서가 다른 모습

그러니 class를 선언할 때 숫자를 기준으로 정렬하되, 같다면 인덱스가 낮은 순으로 정렬되게 설정해야 한다.

---

🌱 느낀 점

 

버블 소트의 개념, 구현을 학부생 때 배워서 쉽게 이해할 수 있었고 응용할 수 있었다, 다시 한번 풀면서

복습하는 느낌이라 정말 도움 됐다, 우선순위큐의 특징, 버블소트 특징을 동시에 배울 수 있어서 좋았다