[코딩 테스트 문제 풀이 시리즈] 10431번 - 줄세우기: 직접 구현부터 삽입 정렬 개념까지

 

문제 개요

 

오늘은 백준 10431번 “줄세우기” 문제를 풀어보았다.

처음 문제를 봤을 때는 단순히 정렬된 결과를 구하는 문제로 생각했지만,

실제로는 학생들이 줄을 서는 과정에서 다른 학생들을 뒤로 밀어내는 횟수를 구하는 것이 핵심이었다.

 

---

처음 내가 작성한 코드

 

처음에는 아래와 같이 구현했다.

학생들을 앞에서부터 차례로 비교하면서, 자기보다 큰 학생이 앞에 있을 경우 그 앞에 끼워 넣고,

뒤에 있던 학생들을 한 칸씩 뒤로 밀어주는 방식으로 정리했다.

import java.util.Scanner;

public class _10431_ {
    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; // 물러난 횟수
            int[] sorted = new int[20]; // 정렬 배열

            for (int i = 0; i < 20; i++) {
                boolean find = false;
                for (int j = 0; j < i; j++) {
                    if (sorted[j] > h[i]) {
                        find = true;
                        for (int k = i - 1; k >= j; k--) {
                            sorted[k + 1] = sorted[k];
                            cnt++;
                        }
                        sorted[j] = h[i];
                        break;
                    }
                }
                if (!find) {
                    sorted[i] = h[i];
                }
            }

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

이 방식은 내가 직접 줄을 세우는 과정을 구현한 것과 같다.

앞에서부터 한 명씩 줄을 세우며 비교하고, 조건에 맞게 정렬과 이동을 동시에 수행했다.

 

---

문제 풀이 중 깨달은 핵심 개념

 

처음에는 로직을 단순히 “정렬 과정에서 몇 명을 뒤로 밀었는지”만을 생각했지만,

풀다 보니 이 과정 자체가 바로 삽입 정렬(Insertion Sort) 과 완전히 동일한 흐름이라는 것을 깨달았다.

 

---

삽입 정렬이란?

 

삽입 정렬(Insertion Sort) 은 배열을 앞에서부터 순차적으로 탐색하면서,

현재 값을 정렬된 부분에서 적절한 위치에 “삽입”하는 방식의 정렬 알고리즘이다.

 

 

작동 방식

1. 두 번째 원소부터 시작해 앞에 있는 원소들과 비교
2. 자신보다 큰 원소들을 한 칸씩 뒤로 밀고
3. 그 자리에 자신을 삽입

초기 배열: [7, 3, 5, 1]
→ 3은 7보다 작으므로 앞에 삽입 → [3, 7, 5, 1]
→ 5는 7보다 작고 3보다 크므로 중간 삽입 → [3, 5, 7, 1]
→ 1은 전부 다 밀고 맨 앞으로 → [1, 3, 5, 7]

 

시간 복잡도

• 최악의 경우 O(N²)
• 하지만 구현이 간단하고, 정렬 과정을 직접 추적해야 하는 문제에 유용하다

---

문제에 적용하기

백준 10431번 문제는 삽입 정렬의 개념을 그대로 적용할 수 있다.

학생들을 앞에서부터 줄 세우며 삽입 정렬을 수행하면,

뒤에 있던 학생들을 뒤로 밀어낸 횟수 = 이동 횟수 = 정답이 된다.

 

문제에서 직접 구현했던 정렬 로직도 결국 삽입 정렬과 동일한 흐름이었다.

처음에는 하나하나 조건을 코드로 구현했지만,

결국은 이미 알고 있는 정렬 알고리즘으로 바꿔보니 코드가 훨씬 더 간단하고 안정적으로 바뀔 수 있다는 걸 깨달았다.

---

추가 팁: 백준 Java 제출 시 주의할 점

 

이번 문제를 처음 풀고 백준에 제출했을 때, 런타임 에러가 발생했다.

 

코드는 완벽하게 동작했는데, 에러의 원인은 단 하나였다.

클래스 이름이 Main이 아니었기 때문이다.

 

백준에서는 내부적으로 Main 클래스를 실행하므로, 반드시 아래와 같이 작성해야 한다.

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

또한 package 선언도 제거해야 정상 제출이 가능하다.

---

마무리

이번 문제를 통해 다음과 같은 중요한 내용을 얻었다.

 

• 문제를 직접 구현해보면서 알고리즘 로직을 눈으로 익힐 수 있었다
• 구현한 방식이 삽입 정렬이라는 걸 깨닫고, 이를 일반화할 수 있었다
• 알고 있는 알고리즘을 실제 문제 풀이에 적용해보는 경험이 중요하다는 걸 알게 되었다
• Java로 백준 문제를 풀 때는 클래스 이름과 패키지에 특히 주의해야 한다

 

단순히 정렬된 결과를 보는 것이 아니라,

정렬이 일어나는 과정과 이동의 의미까지 묻는 문제는 앞으로도 자주 나오기 때문에,

이런 문제에서 삽입 정렬 개념을 활용하는 연습은 반드시 필요하다.