JAVA 백준 10431 줄세우기 (정렬)

 

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

 

---

문제

• 첫째 줄에 테스트 케이스의 P ( 1 <= P <= 1000 ) 이 입력된다.
• 각 테스트케이스 테스트 번호 T와 20개의 양의 정수가 공백으로 구분되어 입력된다.
• 학생이 한 명씩 줄의 맨 뒤에 서면서 두 동작 ( 4, 5 ) 을 반복한다.
• 자기 앞에 자기보다 키가 큰 학생이 있다면 그 자리에 서고 끝난다.
• 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 맨 앞에서 시작하여 가장 처음으로 나오는 학생( A )의 앞에 서고, A부터모든 학생들을 한 칸씩 뒤로 미룬다.
• 모든 테스트 케이스에 대해 각각 테스트 케이스의 번호와 학생들이 한 칸씩 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.

---

 

 

정답 코드

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

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

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

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < P; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            sb.append(st.nextToken()).append(" ");

            ArrayList<Integer> list = new ArrayList<>();

            int count = 0;

            for (int j = 0; j < 20; j++) {
                list.add(Integer.parseInt(st.nextToken()));
                for (int k = 0; k <= j; k++) {
                    if (list.get(j) < list.get(k)) {
                        list.add(k, list.remove(j));
                        count += j - k;
                    }
                }
            }
            
            sb.append(count).append("\n");
        }

        System.out.println(sb);
    }
}

 

 

학생이 한 명 들어올 때마다 들어온 학생과 기존의 학생을 비교하여 매번 정렬하고 걸음수를 셀 수 있도록 한다.