[백준 골드 2] 1377번: 버블 소트

문제

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

1377번: 버블 소트

 

풀이

• 문제의 코드 버블 정렬을 C++로 구현한 알고리즘이다. 버블 정렬에서 swap이 한 번도 일어나지 않은 루프의 위치를 알아내는 코드이다.
• 버블 정렬에서 swap이 일어나지 않은 루프가 존재한다는 것은 정렬이 끝났다는 뜻이다. 그러므로 루프를 알아낸 즉시 반복문을 종료하는 것이 좋다.
• 정렬해야 하는 배열의 크기는 최대 500,000인 자연수이고, 요소의 크기는 최대 1,000,000인 0보다 크거나 같은 자연수이다. 똑같이 버블 정렬을 구현하면 시간 초과가 일어난다.

버블 정렬의 성질에 대해 확실하게 알고 있어야 하는 문제이다.

버블 정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘으로 다음과 같다.

1. 맨 앞에서부터 현재 원소와 다음 원소를 비교한다.
2. 오름차순 정렬을 기준으로 현재 원소가 다음 원소보다 크면 두 원소를 교환한다.
3. 다음 위치로 이동하며 반복한다.

버블 정렬 수행 방식

 

문제의 예제를 버블 정렬하자면 위와 같다.

 

버블 정렬은 원소의 이동이 거품이 수면 위로 올라오는 모습을 닮았다고 해서 지어진 이름이다. 원소의 비교는 왼쪽에서 오른쪽으로 이루어지기 때문에 한 라운드가 끝나면 제일 오른쪽에는 정렬이 완료된 원소만 모인다. 오른쪽으로 원소 이동은 매우 자유롭다는 뜻이다. 하지만 왼쪽으로 원소 이동은 한 라운드에 한 번만 이루어진다. 즉, 원소의 초기 위치와 버블 정렬이 모두 완료된 후 위치를 비교하였을 때, 왼쪽으로 이동한 횟수가 제일 많은 원소는 정렬이 이루어지는 모든 라운드에서 움직였다는 뜻이 된다.

 

예제로 주어진 배열은 [10, 1, 5, 2, 3]이다. 오름차순으로 정렬하면 [1, 2, 3, 5, 10]이 된다.

10은 1번 위치에서 5번 위치로 +4 이동하였다.

1은 2번 위치에서 1번 위치로 -1 이동하였다.

5는 3번 위치에서 4번 위치로 +1 이동하였다.

2는 4번 위치에서 2번 위치로 -2 이동하였다.

3은 5번 위치에서 3번 위치로 -2 이동하였다.

 

음수만큼 이동한 것이 왼쪽으로 이동한 경우이므로 가장 많이 원소가 이동한 경우는 2가 된다. 즉, 완전히 오름차운으로 정렬하는데 총 2 라운드가 소요됐다는 뜻이다. 문제에서는 교환이 일어나지 않는 라운드를 출력하라고 하였으므로 2 라운드 이후 이루어진 3 라운드, 즉 3이 정답으로 출력된다.

 

인덱스가 중요하다는 결론이 내려졌으므로 값과 인덱스를 필드로 가지는 클래스를 정의할 필요가 있다.

public static class Element {
    int value;
    int index;

    public Element(int value, int index) {
        this.value = value;
        this.index = index;
    }

    public String toString() {
        return value + " " + index;
    }
}

 

Element를 타입으로 가지는 ArrayList를 선언하고, value가 큰 순서대로 오름차순 정렬해준다.

ArrayList<Element> arrayList = new ArrayList<>();

for (int i = 0; i < N; i++) {
    arrayList.add(new Element(Integer.parseInt(br.readLine()), i));
}

Collections.sort(arrayList, (Element o1, Element o2) -> {
    return o1.value - o2.value;
});

 

이제 정렬 전후의 인덱스를 비교하며 가장 차이가 큰 값을 구한다.

int max = Integer.MIN_VALUE;
for (int i = 0; i < arrayList.size(); i++) {
    Element e = arrayList.get(i);
    max = Math.max(max, e.index - i);
}

 

마지막으로 max에서 +1을 해준다. 

 

전체 코드 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	public static class Element {
		int value;
		int index;

		public Element(int value, int index) {
			this.value = value;
			this.index = index;
		}
		
		public String toString() {
			return value + " " + index;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<Element> arrayList = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			arrayList.add(new Element(Integer.parseInt(br.readLine()), i));
		}

		Collections.sort(arrayList, (Element o1, Element o2) -> {
			return o1.value - o2.value;
		});
				
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arrayList.size(); i++) {
			Element e = arrayList.get(i);
			max = Math.max(max, e.index - i);
		}
		
		System.out.println(max + 1);
		

	}
}

 

 

후기

정렬, Comparator, Collections 등등 파면 팔수록 궁금한 게 늘어나서 정말 오래 걸렸던 문제였다. 그래도 오래 걸린 만큼 해결했을 때 더욱 뿌듯했다.