[백준/Java] 10431번 줄세우기

-Code

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());

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

            int testNum = Integer.parseInt(st.nextToken());
            int[] childHeight = new int[20];
            int changeCnt = 0;
            for (int i = 0; i < 20; i++) {
                int nowChild = Integer.parseInt(st.nextToken());;
                int targetIdx = -1;
                // 내가 가야하는 자리 찾기
                for (int j = 0; j < i; j++) {
                    if (childHeight[j] > nowChild) {
                        targetIdx = j;
                        break;
                    }
                }
                // 내가 가장 큰 경우
                if (targetIdx == -1) {
                    childHeight[i] = nowChild;
                } else {
                    // 작은 값이 존재하는 경우
                    for (int j = i - 1; j >= targetIdx; j--) {
                        // 뒤에서 부터 1칸씩 뒤로 밀기
                        childHeight[j + 1] = childHeight[j];
                        // 이동 횟수 추가
                        changeCnt++;
                    }
                    // 내가 가야하는 자리에 저장
                    childHeight[targetIdx] = nowChild;
                }
            }

            System.out.println(testNum + " " + changeCnt);
        }
    }
}

한 칸씩 미는 문제인 것은 알아서 배열을 저장 후 2중  for문으로 현재 값보다 큰 경우 뒤에 값을 당겨오는 방식으로 처음에 했으나 데이터 소실이나 로직이 복잡해지는 문제와 값이 하나씩 들어오는 문제인데 이를 재대로 파악못하여 틀렸습니다.

그래서 하나씩 들어오는 것을 인지하고 타깃 위치를 저장하고 그를 기준으로 해결하는 것을  힌트로  얻고 들어오는 값을 StringTokenizer를 통해 하나씩 들어올 때마다 맨 앞부터 현재 순서까지를 검사해 들어갈 위치를 찾고 내가 가장 큰 값이면 현재 위치에 저장하고 아닌 경우 타깃 위치까지 저장된 수를 뒤로 밀어서 해당 위치에 저장할 수 있도록 하여 해결했습니다.