BOJ 10431 : 줄세우기 (C++)

🔷 BOJ 10431 : 줄세우기 (C++)

📌 문제 설명

🔍 문제 상황

초등학교 선생님 강산이는 새 학기가 시작되면 아이들을 키 순서대로 줄세워 번호를 부여합니다.
가장 키가 작은 아이는 1번, 가장 큰 아이는 20번이 됩니다.
항상 반에는 정확히 20명의 학생이 있고, 키가 같은 학생은 없습니다.

하지만 새학기 초에는 아이들이 자신의 정확한 키 순서를 모르기 때문에, 혼란스럽게 줄을 섭니다.

👣 줄 세우는 방식 (삽입 정렬과 유사)

1. 한 명을 먼저 줄의 맨 앞에 세운다.
2. 다음 학생은 항상 줄의 맨 뒤에 와서,
3. 앞에 있는 학생들 중 자신보다 키가 큰 학생이 있다면, 그들 중 가장 앞에 있는 학생(A) 바로 앞에 들어가야 한다.
4. 이때, A부터 뒤의 모든 학생은 뒤로 한 칸씩 밀려야 한다.

❓ 목표

이 과정을 통해 학생들이 줄을 설 때 총 몇 명이 뒤로 밀리는지를 계산하는 문제입니다.

💡 문제 아이디어

이 문제는 사실상 삽입 정렬의 변형입니다.

• arr[k]를 삽입 대상 (pivot)이라고 보고,
• 이 값을 왼쪽에 있는 값들과 비교하여 올바른 위치(min)를 찾고,
• 그 자리에 끼워넣기 위해 나머지 값을 한 칸씩 뒤로 미는 과정을 거칩니다.
• 이때 한 칸씩 밀리는 횟수 = 이동 횟수가 되므로, 그걸 누적합으로 구합니다.

💻 전체 코드

#include <iostream>
using namespace std;

int main(void)
{
    int T; // 테스트 케이스 개수
    cin >> T;

    for (int t = 0; t < T; t++)
    {
        int case_num;
        cin >> case_num;

        int arr[20];
        for (int i = 0; i < 20; i++)
            cin >> arr[i];

        int total_moves = 0;

        for (int k = 1; k < 20; k++)
        {
            int pivot = arr[k];
            int min = k;

            for (int j = k - 1; j >= 0; j--)
            {
                if (pivot < arr[j])
                    min = j;
                else
                    break;
            }

            for (int j = k - 1; j >= min; j--)
                arr[j + 1] = arr[j];

            arr[min] = pivot;
            total_moves += k - min;
        }

        cout << case_num << " " << total_moves << endl;
    }

    return 0;
}

🧠 코드 상세 해설

📌 줄세우기 핵심 로직: for (int k = 1; k < 20; k++)

한 명씩 줄의 뒤에서 앞을 살펴보고 자신의 자리를 찾아 들어가는 과정입니다.

🎬 [k = 19] 일 때 완전 애니메이션 설명

🔹 예제 입력

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

🔸 목표

• pivot = 900을 제자리에 넣는다.
• 앞에 있는 모든 학생들보다 키가 작다.
• 따라서 맨 앞에 서야 하며, 앞에 19명이 전부 한 칸씩 밀려야 함.

📦 배열 상태 (k = 19 시작)

[ 901 ][ 902 ][ 903 ] ... [ 919 ][ 900 ]
                             ↑ k = 19
pivot = 900

🔍 j 비교과정 (하나도 생략하지 않음)

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

j=18: 900 < 919 → min = 18
j=17: 900 < 918 → min = 17
...
j=1: 900 < 902 → min = 1
j=0: 900 < 901 → min = 0

💨 한 칸씩 뒤로 밀기 (arr[j+1] = arr[j])

Step 1: arr[19] = arr[18] → 919 복사
[ ..., 918, 919 ] → [ ..., 918, 918 ]

Step 2: arr[18] = arr[17] → 918 복사
[ ..., 917, 918, 918 ]

...

Step 19: arr[1] = arr[0]
[ 901, 901, ... ]

✅ pivot(900) 삽입

[ 900 ][ 901 ][ 902 ] ... [ 918 ][ 919 ]
          ↑ min

🧮 이동 횟수 계산

total_moves += k - min; // 19 - 0 = 19

✅ 정답 출력 예시

3 19

📚 정리

용어	의미
pivot	현재 삽입 대상 학생의 키
j	앞에서 pivot보다 큰 학생을 찾기 위한 포인터
min	삽입될 위치
이동 수	pivot을 위해 뒤로 밀려난 학생 수 (k - min)

✍️ 마치며

이 문제는 단순한 정렬 문제가 아닙니다.

• 실제 아이들이 줄서며 자리를 찾아가는 과정이
• 삽입 정렬과 어떻게 연결되는지 직접적으로 보여줍니다.
• 이 문제를 풀면서 삽입 정렬의 핵심 원리를
• 직관적으로 이해하게 되는 매우 훌륭한 사례입니다.