[백준/JAVA] 1377 버블소트

[문제]

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

 

[문제 풀이]

버블 소트는 인접한 원소끼리 한 번에 한 칸씩만 교환하면서 정렬을 진행한다. 
즉, 어떤 값이 제자리(정렬됐을 때의 인덱스)보다 뒤쪽(정렬되기 전의 인덱스가 큰 쪽)에 있다면, 한 패스당 한 칸씩 앞으로(인덱스가 작은 쪽으로) 이동하게 된다.

 

 

버블 소트 동작 복기

• 한 패스가 끝나면 가장 큰(혹은 작은) 하나의 원소가 제자리로 간다.
• 각 원소는 본래 위치에서 정렬된 위치까지 ‘인접 교환’으로만 이동하므로, 패스 수 = 그 요소가 이동해야 하는 칸 수

 

버블 소트는 정렬이 마무리 된 상태에서 정렬이 마무리가 됐는지 확인을 한 번하고 정렬이 됐으면 정렬을 마치므로, 
이 문제는 버블 정렬이 몇 번 일어나는지를 묻는 문제이기 때문에 마지막에 +1을 더해줘야 한다.

[정답 코드]

package bubleSort;

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

public class Boj_1377 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		Num[] arr = new Num[n];
		for(int i=0; i<n; i++) {
			arr[i] = new Num(i, Integer.parseInt(br.readLine()));
		}

		Arrays.sort(arr, (x,y) -> x.value - y.value);
		
		int answer = 0;
		
		for(int i=0; i<n; i++) {
			int diff = arr[i].idx - i;
			answer = Math.max(diff, answer);
		}
		
		System.out.println(answer+1);
	}
	
	static class Num{
		int idx;
		int value;
		
		Num(int idx, int value){
			this.idx = idx;
			this.value = value;
		}
	}

}