백준 10431 줄세우기 JAVA 풀이 (구현, 정렬, 시간복잡도)

🔗 문제 링크

https://www.acmicpc.net/problem/10431

---

📌 문제 개요

백준 10431번은 학생들이 줄을 설 때 발생하는 이동 횟수의 총합을 구하는 문제

학생들은 순서대로 줄에 들어오며,

자신보다 키가 큰 학생보다 앞에 서야 합니다.

이 과정에서 발생하는 이동 횟수를 모두 더하는 것이 목표입니다.

---

📌 접근 방법

이 문제는 실제로 학생을 이동시키는 것보다,
이동 횟수를 계산하는 것이 핵심 학생이 들어올 때마다:

• 이미 들어온 학생들 중에서
• 자신보다 키가 큰 학생 수를 세면 됨

이 값이 곧 이동 횟수

---

📌 핵심 아이디어

이동 횟수의 의미

현재 학생 기준 : 앞에 있는 학생 중 나보다 큰 학생 수 = 이동 횟수

---

예시

입력 : 5 3 4 2

 

진행:

• 5 → 이동 없음
• 3 → 5보다 작음 → 1칸 이동
• 4 → 5보다 작음 → 1칸 이동
• 2 → 5,3,4보다 작음 → 3칸 이동

총 이동 = 1 + 1 + 3 = 5

---

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

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

            int caseNum = Integer.parseInt(st.nextToken());
            int[] arr = new int[20];

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

            int count = 0;

            for (int i = 0; i < 20; i++) {
                for (int j = 0; j < i; j++) {
                    if (arr[j] > arr[i]) {
                        count++;
                    }
                }
            }

            System.out.println(caseNum + " " + count);
        }
    }
}

 

---

📄 정리

이 문제는 정렬처럼 보이지만 실제로는 이동 횟수만 계산하는 구현 문제

• 앞에 있는 학생만 비교하면 된다
• 나보다 큰 학생 수를 세면 된다
• 실제 이동은 필요 없다
• 시간복잡도: O(N²) (N=20 → 충분히 빠름)