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

1377번 : 버블 소트 (https://www.acmicpc.net/problem/1377)

---

문제

---

접근 방법

---

• 문제에서 주어진 코드는 버블 정렬이 끝났을 때 몇 번째 i 반복에서 끝났는가를 구하는 코드이다.

• 버블 정렬은 인접한 수끼리 비교하여 정렬 조건에 맞지 않으면 서로의 위치를 swap 하여 정렬하는 방법이다.

  • 버블 정렬에 관한 자세한 내용은 여기

• 이 문제에서 실제로 O(n²)의 시간 복잡도를 가지는 버블 정렬을 실행하여 실행 횟수를 카운트하는 경우, N <= 500,000이기 때문에 시간 제한에 걸리게 된다. 따라서 다른 방법을 이용하여 해결해야 한다.

• 코드에서 하나의 i에서 하나의 수가 정렬된다. 이때 정렬되는 수가 오른쪽으로 움직이기 때문에 다른 수들은 왼쪽으로 밀리게 되는데, 밀리는 수는 하나의 i에서 최대 1만큼 왼쪽으로 움직여질 수 있다.

• 따라서 왼쪽으로 최대로 움직인 수가 움직인 거리만큼 i 반복문을 실행한 것이기 때문에 왼쪽으로 움직인 거리의 최댓값을 구해야 한다.

• 값의 정렬 전 위치와 정렬 후 위치를 구한 후, 현재 위치 - 이전 위치를 계산하면 왼쪽으로 움직인 수는 음수를 갖는다. 그렇기 때문에 왼쪽으로 움직인 거리의 최댓값을 찾기 위해서 현재 위치 - 이전 위치의 최솟값을 찾으면 된다.

  • 정렬 후 위치를 찾을 때 사용한 정렬은 O(nlogn)을 시간 복잡도로 가지는 Arrays.sort() 사용

• 이동 거리의 최솟값을 구한 후, 양수로 변환한 값에 +1을 하여 출력한다.

  • +1을 하는 이유 ⇒ 정렬이 끝난 후에도 한 번 더 i 반복문이 돌기 때문이다.

코드

---

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

public class Main {
	static class Node implements Comparable<Node> {
		int idx;
		int value;

		Node(int idx, int value) {
			this.idx = idx;
			this.value = value;
		}

		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Node[] arr = new Node[N];
		for (int i = 0; i < N; i++) {
			arr[i] = new Node(i, Integer.parseInt(br.readLine()));
		}
		Arrays.sort(arr);
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			min = Math.min(min, i - arr[i].idx);
		}
		System.out.println(-1 * min + 1);
		br.close();
	}
}

위의 코드의 성능

정리

---

버블 정렬에서 인접한 수가 swap 되며 오른쪽부터 정렬된다는 특징을 알고, 왼쪽으로 움직인 값의 이동 거리의 최댓값이 답이라는 것을 알아내는 것이 포인트였다.