[백준][java] 10431 - 줄세우기

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

10431번: 줄세우기

난이도 : S5

유형 : 시뮬레이션, 이분 탐색

시간 : P * NlogN  (P <= 1000, N <= 20)

---

문제 풀이

 

새롭게 줄을 서는 아이의 키보다 큰 아이가 이미 앞에 서있다면 그 아이의 위치를 알아야 한다.

위치를 알아내는 방법 중 완전 탐색이 아닌 이분 탐색으로 찾으면 더 빠르게 찾을 수 있다.

(이 문제의 테스트의 입력값이 널널하여 완전탐색가 크게 차이 나지 않는다)

 

필자는 lowerBound 메소드를 직접 구현하여 이분 탐색을 진행했다.

 

새롭게 줄을 서려는 아이보다 첫 번째로 큰 아이의 위치를 알아내고

그 위치와 현재 서있는 줄의 길의 차를 계속 누적해주면 된다.

그 후 알아낸 위치에 새롭게 아이를 세우면 된다.

 

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

/*author : DDing77*/

public class Main {

    private int P;
    private int tCase;
    private ArrayList<Integer> line;
    private int res;

    public int lowerBound(ArrayList<Integer> line, int target) {
        int left = 0;
        int right = line.size();
        int mid;

        while (left < right) {
            mid = left + right >> 1;
            if (line.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        P = Integer.parseInt(br.readLine());
        while (P-- > 0) {
            st = new StringTokenizer(br.readLine());
            tCase = Integer.parseInt(st.nextToken());

            res = 0;
            line = new ArrayList<>();
            while (st.hasMoreTokens()) {
                int cur = Integer.parseInt(st.nextToken());

                if (line.isEmpty() || line.get(line.size() - 1) < cur) {
                    line.add(cur);
                    continue;
                }

                int targetIdx = lowerBound(line, cur);

                res += (line.size() - targetIdx);
                line.add(targetIdx, cur);
            }

            sb.append(tCase).append(" ").append(res).append('\n');
        }

        System.out.print(sb);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}