[코딩테스트] 줄 세우기 (삽입 정렬)

문제

초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.

하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.

우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.

자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.
이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.

아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?

입력

첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.

각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.

20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.

모든 테스트 케이스는 독립적이다.

출력

각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.

예제 입력 1

4
1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900
3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900
4 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 919

예제 출력 1

1 0
2 190
3 19
4 171

생각

• 2번째 사람부터 키 순으로 자신의 위치를 찾아 삽입하는 방식이므로 삽입 정렬을 구현하면 되는 문제였다
• 자신보다 큰 최초의 위치를 찾고(pos, 만약 못 찾으면 자기 자신) 자신 ~ pos까지의 위치를 뒤로 한 칸씩 밀어 line[j] = line[j - 1]; 삽입 정렬을 구현하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class LineUp {

    public int getMoveBackCnt(int[] tc) {
        int[] line = new int[21];
        int backCnt = 0;

        for (int i = 1; i <= 20; i++) {
            int cur = tc[i];
            int pos = 1;
            while (pos < i && line[pos] < cur) {
                pos++;
            }

            for (int j = i; j > pos; j--) {
                line[j] = line[j - 1];
            }

            line[pos] = cur;
            backCnt += (i - pos);
        }

        return backCnt;
    }

    public static void main(String[] args) throws IOException {
        LineUp T = new LineUp();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int P = Integer.parseInt(br.readLine());

        for (int i = 0; i < P; i++) {
            int[] tc = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            System.out.println(tc[0] + " " + T.getMoveBackCnt(tc));
        }

    }
}

정리

• 삽입 정렬 알고리즘

1. 배열의 첫 번째 요소를 이미 정렬된 것으로 간주
2. 다음 요소를 선택하고 이미 정렬된 배열 부분에서 올바른 위치를 찾아 삽입
3. 모든 요소 선택될때까지 2단계 반복

• 삽입 정렬 시간 복잡도
  최악의 경우 O(N^2)에 해당. 최악의 경우 모든 이전 요소와 비교를 해야 한다. 하지만 배열이 거의 정렬된 경우, O(N) 의 최선의 시간 복잡도를 가질 수 있다
  -> 작언 데이터 set나 거의 정렬된 데이터를 대상으로 효율적이나, 데이터의 사이즈가 크거나, 정렬이 잘 되어있지 않은 경우 퀵 정렬 등의 다른 알고리즘을 사용하는 것이 더 효율적!

---

문제 출처