문제

초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.

하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.

우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.

1) 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
2) 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.
이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.

아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?

입력

첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.

각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.

20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.

모든 테스트 케이스는 독립적이다.

출력

각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.

예제 입력

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

예제 출력

1 0
2 190
3 19
4 171

내가 했던 풀이 방법

1. 입력받은 숫자를 list에 저장한다. (이때 1번째 인덱스부터 20까지 저장해야 한다. 처음에 입력받은 숫자는 테스트 케이스 번호 때문에.)

2. current(현재 인덱스)를 1부터 시작해서 반복문을 끝낼 때마다 1씩 증가시킨다. current가 20이상이 되어버리면 반복문을 탈출한다. (1부터 시작하는 이유는 0번째는 어떤 행동없이 바로 끝나기 때문에 무시해도 됨, 중간에 current값을 변경시키므로 1씩 증가시켜도 무관함)

3. 0부터 current까지 for문을 돌린다. 이때, current의 값보다 더 큰 값이 list에 있을 경우 current를 자신보다 큰 값 앞에 위치시켜주고, 이동해야 하는 횟수만큼 count를 증가시켜주고, current를 j(현재 for문 값)으로 바꿔준다. (위치가 변경된 뒤부터 다시 정렬을 해줘야하기 때문에)

4. 반복문이 탈출되었으면 테스트 케이스 번호와 count를 출력해준다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cases = Integer.parseInt(br.readLine());

        String[] input;
        ArrayList<Integer> list = new ArrayList<>();
        int current;
        int current_h;
        int count;
        for(int i=0; i<cases; i++) {
            count = 0;
            current = 1;
            list.clear();
            input = br.readLine().split(" ");
            for(int j=1; j<=20; j++) {
                list.add(Integer.parseInt(input[j]));
            }

            while(true) {
                if(current>=20) {
                    break;
                }

                for(int j=0; j<current; j++) {
                    current_h = list.get(current);
                    if(current_h<list.get(j)) {
                        count = count+current-j;
                        list.remove(current);
                        list.add(j, current_h);
                        current = j;
                    }
                }

                current++;
            }

            
            System.out.println(i+1 + " " + count);

        }
        
    }   
}

회고

설명하기가 조금 난해..하지만 문제에서 제시한 방식을 그대~로 작성하면 된다. 다른 코드를 보니 버블 정렬/내 앞에 나보다 더 큰 사람의 수의 합으로 계산하던데 바로 그 방법을 떠올리기엔 어려움이 있어서 문제에서 제시한 그대로 풀이했다.
문제 자체가 별로 마음에 들진 않는다. "자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다."라는 방법에서 나처럼 현재 정렬된 줄에 맨 앞으로 이동한다고 착각하게 만든 것 같기도 하고.. 제대로 읽지 않은 내 잘못이지만 조금 더 명확했으면 좋지 않았을까 예제 케이스에서도 이를 유추할 수 있게라도 해줘야 하지 않았을까..라는 생각이 들었다. (ㅂㄷㅂㄷ)
심지어 모든 테스트 케이스가 제대로 출력되는데(반례도 몇 개 없어서 정답 코드를 복사해와서 내 코드랑 출력을 비교해봤음..) 자꾸 25%에서 틀렸다고 해서 포기할까 정말 많이 고민했는데 알고보니 줄바꿈을 하지 않아서였다고.. 그래서 1시간 넘게 고민했던게 약간 화가 날 정도로 어이없는 실수...ㅜㅜ 최근 백준 중에 제일 열불 났던 문제지만 풀이했으니 뭐~