배열_백준_10431_줄 세우기

10431번: 줄세우기

문제 해석

애들의 키를 오름 차순으로 만들면 된다. 내 앞 숫자가 나보다 크다면 앞으로 가고 작다면 가만히 있으면 된다.

이때 내가 앞으로 가야한다면 나보다 큰 애들은 한발자국씩 뒤로 움직여야할테니 그 숫자를 체킹해야한다.

접근

간단하다, 해당 숫자와 배열에 미리 들어가있는 숫자들을 비교해서 해당 숫자보다 큰 수만큼 +해주면 된다.

대충 코드를 짜보면

int[] h = new int[20];
for (int i = 0; i < 20; i++) {
    h[i] = sc.nextInt();
}

int ans = 0;
for (int i = 0; i < 20; i++) {
    for (int j = 0; j < i; j++) {
        if (h[j] > h[i]) {
            ans++;
        }
    }
}

이런식으로 짜면 원하는 값이 나오긴 하는데.. 이중 반복문은 시간 복잡도가 O(n^2)이 된다. 지금은 배열이 20으로 고정되어있긴 하지만 학생이 10만명이면 시간복잡도도 10만의 제곱이 나오고 정답의 범위도 50억 가까이 되기 때문에 Integer의 범위를 아득히 벗어나게 된다.

그러니까 더 효율적인 코드를 만들어보자.

문제풀이

테스트 케이스 받는법

테스트의 수를 먼저 받고 하나씩 줄어들면서 모든 테스트를 소모하면 멈추도록 while문을 통하여 반복

int P = sc.nextInt(); // 테스트 케이스의 수
while (P-- > 0) { // 테스트 케이스가 모두 소모되면 반복 종료함
    int T = sc.nextInt(); // 테스트 케이스 번호
    int[] h = new int[20];
    for (int i = 0; i < 20; i++) {
        h[i] = sc.nextInt();
    }
}

package learnString;

import java.util.Scanner;

class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int P = sc.nextInt();
        while (P-- > 0) {
            int T = sc.nextInt();
            int[] h = new int[20];
            for (int i = 0; i < 20; i++)
                h[i] = sc.nextInt();

            int cnt = 0;
            for (int i = 0; i < 20; i++) {
                for (int j = 0; j < i; j++) {
                    if (h[j] > h[i]) {
                        int myH = h[i];
                        for (int k = i; k > j; k--) {
                            h[k] = h[k - 1];
                            cnt++;
                        }
                        h[j] = myH;
                        break;
                    }
                }
            }
            System.out.println(T + " " + cnt);
        }
    }
}