[백준/구현] 10431 줄세우기(Java, 자바)

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

10431번: 줄세우기

 

 

단순하게 생각하면 금방 풀 수 있다.

 

예를 들어 

6 2 3 7 5 1 4 로 주어졌을 때,

각 학생이 옮겨지는 횟수는 자신보다 앞에 있는 수 중에서 자신보다 큰 수의 개수이다.

 

위의 예시로 봤을 때 다음 표와 같이 된다.

키	6	2	3	7	5	1	4
옮겨지는 횟수	0	1	1	0	2	5	3

여기서 옮겨지는 횟수를 모두 더하면 된다.

 

코드로 옮겨보면 간단하다.

int cnt = 0;

for (int i = 0; i < 20; i++) {
    for (int j = 0; j < i; j++) {
        // 앞에 큰 수가 있는지 확인
        if (height[i] < height[j])
            cnt++;
    }
}

 

 

전체코드는 다음과 같다.

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int[] height;

    static void input() {
        height = new int[20];

        for (int i = 0; i < 20; i++) {
            height[i] = scan.nextInt();
        }
    }

    static int pro() {
        int cnt = 0;

        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < i; j++) {
                // 앞에 큰 수가 있는지 확인
                if (height[i] < height[j])
                    cnt++;
            }
        }

        return cnt;
    }

    public static void main(String[] args) {
        int P = scan.nextInt();

        while (P-- > 0) {
            int T = scan.nextInt();
            input();
            System.out.println(T + " " + pro());
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}