BOJ 10431 : 줄세우기 (Python)

🔷 BOJ 10431 : 줄세우기 (Python)

📌 문제 설명

초등학교 선생님 강산이는
아이들을 키 순서대로 줄 세우는 일을 매년 합니다.
항상 반에는 20명의 학생이 있고,
같은 키를 가진 학생은 없습니다.

👣 줄 세우는 규칙

1. 맨 앞에 한 명을 세운다.
2. 그다음 학생은 항상 줄의 맨 뒤에 선다.
3. 앞에 자기보다 키가 큰 학생이 있다면, 그중 가장 앞에 있는 학생의 앞에 끼어든다.
4. 이때, 그 학생부터 뒤쪽 모든 학생은 한 칸씩 뒤로 밀려난다.

🎯 목표

모든 학생이 줄을 선 후,
총 몇 명의 학생이 뒤로 밀려났는지를 출력하시오.

💡 문제 풀이 방법

• 각 학생을 순서대로 배열에 삽입한다.
• 삽입할 때마다 왼쪽을 보면서 자신보다 키가 큰 학생을 찾는다.
• 그 앞에 끼어들기 위해, 다른 학생들을 한 칸씩 오른쪽으로 밀어낸다.
• 밀린 횟수를 모두 합친다.

💻 전체 코드

T = int(input())

for _ in range(T):
    data = list(map(int, input().split()))
    case_number = data[0]
    arr = data[1:]

    total_move = 0

    for k in range(1, 20):
        pivot = arr[k]
        min_index = k

        # 자기보다 큰 학생을 왼쪽에서 찾는다
        for j in range(k - 1, -1, -1):
            if pivot < arr[j]:
                min_index = j
            else:
                break

        # 뒤로 밀기 (오른쪽으로 shift)
        for j in range(k - 1, min_index - 1, -1):
            arr[j + 1] = arr[j]

        # 빈 자리에 pivot 삽입
        arr[min_index] = pivot

        # 이동한 학생 수 계산
        total_move += (k - min_index)

    print(case_number, total_move)

🔍 코드 설명

🔸 입력 처리

T = int(input())

테스트 케이스 개수를 입력받는다.

data = list(map(int, input().split()))
case_number = data[0]
arr = data[1:]

각 테스트 케이스에서 번호와 키 정보를 읽는다.

🔸 줄 세우기 과정 (삽입)

for k in range(1, 20):

두 번째 학생부터 시작해서 하나씩 줄을 선다.

pivot = arr[k]
min_index = k

지금 줄 서려는 학생의 키를 pivot이라고 한다.
처음엔 자기 자리에 그대로 설 거라고 가정한다.

🔸 왼쪽 탐색

for j in range(k - 1, -1, -1):
    if pivot < arr[j]:
        min_index = j
    else:
        break

왼쪽으로 가면서 pivot보다 키가 큰 학생을 찾는다.
가장 앞에 있는 큰 학생 앞에 서야 하므로,
그때의 위치를 min_index로 기억해둔다.

🔸 뒤로 밀기

for j in range(k - 1, min_index - 1, -1):
    arr[j + 1] = arr[j]

pivot을 끼워넣기 위해,
뒤쪽 학생들을 한 칸씩 오른쪽으로 민다.

🔸 pivot 삽입

arr[min_index] = pivot

이제 자리가 났으니 그 자리에 서게 한다.

🔸 이동 수 계산

total_move += (k - min_index)

몇 명을 민 것인지 계산해서 total_move에 더한다.

🔸 출력

print(case_number, total_move)

🧪 예제 실행

입력:

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

출력:

3 19

→ 맨 마지막 학생 900이 맨 앞에 끼어들며,
→ 앞의 19명이 한 칸씩 밀렸다.

📚 정리

변수명	설명
pivot	지금 줄서려는 학생의 키
min_index	끼어들 자리 위치
j	왼쪽을 순회하며 비교하는 인덱스
arr	줄서기 진행 중인 배열
total_move	밀린 학생들의 총합

✍️ 마무리

이 문제는 삽입 정렬이 현실 상황에서 어떻게 쓰일 수 있는지를 보여주는 문제입니다.
아이들이 줄을 서는 행동을 그대로 코드로 옮겨보며,
정렬 알고리즘의 동작 원리를 직관적으로 이해할 수 있습니다.