[Kotlin, S5] 백준 30010번 잘못된 버블정렬

출처: unsplash.com

 

잘못된 버블정렬(30010번)

Silver 5

#애드 혹 #해 구성하기

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

 

문제 내용

 

 

문제 접근

위 문제에 잘못된 방식으로 구현된 버블 정렬 함수가 있다.

이 함수를 이용해 버블 정렬을 했을 때, 올바르게 정렬되지 않는 리스트를 출력하면 된다.

 

먼저 버블 정렬이 어떻게 이루어지는지 알아야 한다.

버블 정렬은 현재 위치에서 자신의 앞의 값을 확인해서 자신보다 값이 작을 경우 서로의 값을 교환하는 방식으로 구현을 한다.

물론 1번의 사이클로는 정렬이 바로 안 되는 경우가 많기 때문에 정렬할 List의 크기만큼 반복해 주면 정렬을 마칠 수 있다.

출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

size가 5인 List를 4번의 사이클을 돌아 정렬을 완료한 부분이다.

현재 자신의 앞의 값을 확인하고 있기 때문에 앞의 값이 현재 자신보다 더 작으면 값을 서로 교환하는 방식으로 구현한다.

자세한 설명은 아래의 블로그 글을 참고해서 문제의 코드가 잘못된 원인을 분석해 보자.

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

 

문제의 코드는 값 확인을 마지막 index부터 0번째 index까지 반복하고 있다.

내부 반복문에서 이미 정렬된 값인 i번째 index 이전부터 검색하는 것도 잘 구현했다. 앞의 값이 더 작은 경우 데이터를 교환하는 것도 문제가 없다.

 

문제의 코드를 자세히 살펴보면 문제점을 찾을 수 있을 것이다. 사이클의 순서를 역순으로 보고 있는 건 상관없다.

하지만 사이클을 역순으로 보고 있는데 안쪽 반복문은 마지막 값을 제외시키고 있다.

사이클이 역순으로 돌고 있으면 내부의 반복문도 마지막 값이 아닌 첫 번째 값부터 제외시켰어야 정렬이 올바르게 동작한다.

 

N = 5일 때

5 4 3 2 1

1 5 4 3 2	// i = 4, j = 3
1 3 5 4 2	// i = 3, j = 2
1 3 5 4 2	// i = 2, j = 1
1 3 5 4 2	// i = 1, j = 0

아래 N이 5일 때 반복에 따른 i과 j값과 정렬 결과를 나열한 결과이다.

j의 값은 i의 값에 의해 변경된다. 안쪽 반복은 j번째 index부터 0까지 반복된다.

첫 번째 사이클에서는 3번째 index부터 0번째 index까지 확인했다. 첫 사이클에서는 내부 반복문 내부에서 j + 1을 이용해 마지막인 4번째 index까지 확인했으므로 문제가 없다.

두 번째 사이클에서는 j가 2이기 때문에 j + 1을 해도 3번째 index까지밖에 볼 수 없다. 현재 정렬을 작은 값을 앞으로 보내는 정렬을 하고 있는데 마지막 index를 제외시키고 있으니 정렬이 제대로 될 리가 없다.

 

이로 인해 위 코드의 반례는 가장 큰 값이 0번째 index로 올 경우, 사이클을 돌면서 1칸씩 뒤로 이동한다고 해도 제외된 부분 때문에 제일 큰 값이 리스트의 맨 뒤로 이동하지 못한다. 위의 N = 5일 때의 예제도 그렇지 않은가?

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    val result = StringBuilder()

    for (i in size downTo 1) {
        result.append("$i ")
    }

    println(result)
}

 

문제 풀이

문제 접근에서 파악한 문제로는 0번째 index에 제일 큰 값이 들어오게 되면 문제의 코드로는 정렬이 불가능하다는 사실을 알게 되었으니, size의 역순으로 값을 출력해 주면 정답이 된다.

 

 

문제 해결 과정

버블 정렬 이해도 테스트.

버블 정렬이 어떻게 동작하는지 파악해 문제 코드의 문제점을 파악해 올바른 반례를 생각해야 한다.

나는 버블 정렬의 개념을 찾아보고 나서 문제를 해결했다.

 

그냥 문제점을 파악하지 않고 리스트의 값을 shuffle 해서 랜덤 하게 값을 들어가게 한 후, 정렬이 제대로 되지 않는 리스트를 출력해도 된다. 하지만 버블 정렬의 특징을 잘 파악해서 문제점을 찾아서 해결하는 방법이 공부에 더 도움이 될 것이다.