문제 설명

초등학교 선생님 강산이는 새로 반에 배정받은 아이들을 키 순서대로 줄 세우기 하려고 한다.
하지만 처음에는 아이들이 자신의 정확한 위치를 알지 못하기 때문에 다음 방법으로 줄을 세운다.

1. 첫 번째 학생을 줄 맨 앞에 세운다.
2. 이후 학생들은 줄의 맨 뒤에 먼저 선다.
3. 자신의 앞에 자기보다 키가 큰 학생이 없다면 그대로 서 있는다.
4. 만약 자기보다 키가 큰 학생이 있다면
   그중 가장 앞에 있는 학생 바로 앞에 위치한다.
5. 이때 밀린 학생들은 뒤로 한 칸씩 물러난다.

이 과정을 모든 학생에 대해 반복했을 때,
학생들이 뒤로 물러난 총 횟수를 구하는 문제이다.

---

입력

첫째 줄에는 테스트 케이스의 수

P

각 테스트 케이스는 다음과 같이 주어진다.

T h1 h2 h3 ... h20

• T : 테스트 케이스 번호
• h1 ~ h20 : 학생들의 키

조건

1 ≤ P ≤ 1000

학생 수는 항상

20명

이다.

---

출력

각 테스트 케이스에 대해

테스트번호 이동횟수

형식으로 출력한다.

---

입력 예시

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 0
2 190
3 19
4 171

---

문제 해결 아이디어

이 문제는 삽입 정렬(Insertion Sort) 방식과 동일한 원리로 해결할 수 있다.

학생이 줄 뒤에 서면

앞에 있는 학생들과 비교

하면서 자신보다 키가 큰 학생을 찾는다.

만약 발견되면

그 학생 앞에 들어가고
그 뒤의 학생들은 한 칸씩 뒤로 이동

하게 된다.

이때 뒤로 이동한 횟수를 모두 더하면 정답이 된다.

---

내가 작성한 풀이

나는 배열에 학생들을 하나씩 삽입하면서
들어가야 할 위치를 찾고 배열을 직접 밀어주는 방식으로 구현했다.

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int tc = sc.nextInt();
        sc.nextLine();

        int[] result = new int[tc];

        for(int i = 0; tc > i; i++) {

            String[] inputString = sc.nextLine().split(" ");

            int count = 0;
            int[] input = new int[20];
            int index = -1;

            for(int j = 0; j < 20; j++) {

                int tmp = Integer.parseInt(inputString[j+1]);

                for(int k = j-1; k >= 0; k--) {

                    if(tmp < input[k])
                        index = k;
                }

                if(index != -1) {

                    count += j - index;
                    insertElement(input, j, index, tmp);

                } else {

                    input[j] = tmp;

                }

                index = -1;
            }

            result[i] = count;

        }

        for(int i = 0; tc > i; i++) {

            System.out.println(i+1 +" "+result[i]);

        }
    }

    public static boolean insertElement(int[] arr, int arrCount, int idx, int val) {

        if (idx > arrCount || arrCount >= arr.length)
            return false;

        for (int i = arrCount; i > idx; i-- )
            arr[i] = arr[i-1];

        arr[idx] = val;

        return true;
    }
}

이 방법은

삽입 위치 탐색
→ 배열 밀기
→ 이동 횟수 계산

순서로 구현하였다.

---

강의 풀이

강의에서는 삽입 정렬 방식으로
학생을 한 명씩 앞과 비교하면서 위치를 찾는다.

코드

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int P = sc.nextInt();

        while (P-- > 0) {

            int T = sc.nextInt();

            int[] h = new int[20];

            for (int i = 0; i < 20; i++)
                h[i] = sc.nextInt();

            int cnt = 0;

            for (int i = 0; i < 20; i++) {

                for (int j = 0; j < i; j++) {

                    if (h[j] > h[i]) {

                        int myH = h[i];

                        for (int k = i; k > j; k--) {

                            h[k] = h[k - 1];
                            cnt++;

                        }

                        h[j] = myH;

                        break;

                    }

                }

            }

            System.out.println(T + " " + cnt);

        }

    }
}

---

두 풀이 방식 비교

방식	특징
내 풀이	삽입 위치를 먼저 찾고 배열 이동
강의 풀이	비교하면서 바로 삽입

두 방식 모두

삽입 정렬 원리

를 기반으로 구현되었다.

---

시간 복잡도

학생 수는 항상

20명

이다.

삽입 정렬의 시간 복잡도

O(N²)

이지만

20 × 20 = 400

이므로 충분히 빠르게 실행된다.

---

핵심 개념

이 문제의 핵심은 다음이다.

1. 삽입 정렬(Insertion Sort) 원리
2. 앞에 있는 학생들과 비교
3. 더 큰 학생 앞에 삽입
4. 밀린 횟수 누적

---

정리

이 문제는 단순한 정렬 문제가 아니라
삽입 정렬 과정에서 발생하는 이동 횟수를 구하는 문제였다.

학생이 줄 뒤에 서면 앞의 학생들과 비교하면서
자기보다 큰 학생 앞에 들어가고,
그 과정에서 밀린 학생들의 횟수를 모두 더하면 정답이 된다.

즉,

삽입 정렬 과정에서 발생하는 이동 횟수

를 계산하는 문제라고 볼 수 있다.