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

문제

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

10431번: 줄세우기

 

풀이

문제 잘 읽고 구현하면 됨!

아마 ArrayList나 List 등을 이용하여 많이들 구현할 것 같은데 그렇게 할 경우 애들을 줄 세울 때 어디에 세워야하는지가 조금 헷갈릴 수도 있으니 주의할 것!

자세한건 주석에 있음

 

코드

// 10431번 줄세우기
// https://www.acmicpc.net/problem/10431

package BAEKJOON;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Num10431_줄세우기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            Queue<Integer> queue = new LinkedList<>(); // 줄 세울 애들
            ArrayList<Integer> arrayList = new ArrayList<>(); // 줄 선 애들
            st.nextToken(); // 걍 쓸데없는거. 어차피 밑에서 t로 번호 출력해줄거임

            // 큐에 입력해줌
            for (int i = 0; i < 20; i++) {
                queue.offer(Integer.parseInt(st.nextToken()));
            }

            // 애들이 몇걸음 뒤로 갔는지 count
            int count = 0;

            // 첫번째 애는 일단 줄을 세움
            arrayList.add(queue.poll());

            while (true) {
                // 줄 세울 애들이 없을 때까지 반복
                if (queue.isEmpty()) {
                    break;
                } else {
                    for (int j = 0; j < arrayList.size(); j++) {
                        // 줄 서있는 애가 줄 세우려고 하는 애보다 크면
                        if (arrayList.get(j) > queue.peek()) {
                            // 줄 서있는 애부터 맨 뒤에 애까지 한 걸음 뒤로가야되니까 그만 큼 count에 더해줌
                            count += arrayList.size() - j;
                            
                            // 그 줄 서있는 애 앞에가서 서면 됨 
                            arrayList.add(j, queue.poll());
                            
                            break;
                        } else if (j == arrayList.size() - 1) { // 줄 세우려고 하는 애가 줄 서있는 애들보다 커서 맨 뒤에 서는 경우
                            arrayList.add(arrayList.size(), queue.poll());
                            break;
                        } else { // 줄 못 세웠으면 다음 줄 서있는 애랑 비교하기 위해 continue
                            continue;
                        }
                    }
                }
            }

            sb.append(t).append(" ").append(count).append("\n");
        }

        sb.setLength(sb.length() - 1);
        
        System.out.println(sb);
    }
}