줄세우기 (BOJ 10431)

줄세우기 (BOJ 10431)

📖 문제 설명

학생 20명의 키가 주어진다.

앞에서부터 한 명씩 줄에 세울 때, 이미 서 있는 학생들 중에서 자기보다 키가 큰 학생 앞에 삽입된다.

이때 뒤로 밀려난 학생들의 총 이동 횟수를 구하는 문제이다.

✅ 조건 정리

• 한 테스트 케이스당 학생 20명

• 학생은 주어진 순서대로 한 명씩 줄에 선다

• 자기보다 키가 큰 학생 앞에 삽입

• 뒤로 밀린 학생 수를 모두 더한 값 출력

• 출력 형식:

💡 풀이 방법

1️⃣ 접근 아이디어

실제로 줄을 구현하지 않아도 된다.

핵심은:

🔥 현재 학생보다 앞에 있으면서 키가 더 큰 학생 수를 세면 된다.

왜냐하면,

그 학생들은 결국 삽입 시 뒤로 밀려야 하는 학생들이기 때문이다.

즉,

이동 횟수 =
앞에 있는 나보다 키 큰 학생 수

2️⃣ 핵심 로직 설명

1. 학생 키를 배열에 저장

2. i번째 학생을 처리할 때

3. 0 ~ i-1 구간에서

4. 현재 학생보다 키가 큰 사람 수를 카운트

예시:

150 160 155

• 150 → 이동 0

• 160 → 이동 0

• 155 → 앞에 160이 더 큼 → 이동 1

총 이동 횟수 = 1

💻 코드

package boj;

import java.io.*;
import java.util.*;

public class Boj10431 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int t = 1; t <= testCase; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int caseNum = Integer.parseInt(st.nextToken()); // 테스트 번호
            int[] arr = new int[20];
            int moveCount = 0;

            for (int i = 0; i < 20; i++) {
                arr[i] = Integer.parseInt(st.nextToken());

                // 현재 학생(arr[i])보다 앞에 있으면서 키 큰 학생 수 세기
                for (int j = 0; j < i; j++) {
                    if (arr[j] > arr[i]) {
                        moveCount++;
                    }
                }
            }

            sb.append(caseNum).append(" ").append(moveCount).append("\n");
        }

        System.out.print(sb);
    }
}

⏱ 시간 복잡도

• 시간복잡도: O(N²)

• 공간복잡도: O(N)

※ N이 20으로 고정이기 때문에 사실상 상수 시간에 가깝다.

🔎 배운 점 / 느낀 점

• 실제로 삽입을 구현하지 않아도 결과를 계산할 수 있다.

• 이 문제는 “삽입 정렬” 개념과 동일하다.

• 앞쪽에 있는 더 큰 값의 개수를 세는 문제로 단순화할 수 있다.

• 이는 역순쌍(Inversion) 개념과도 연결된다.