ACM ICPC 2000 ASIA Problem A Car Racing

ProgrammingAlgorithm
Algorithm, ICPC, Programming

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.Arrays;
import java.util.Scanner;
public class CarRacing {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt(); // 테스트 케이스의 개수
        for (int i = 0; i < T; i++) {
            int N = scan.nextInt(); // 자동차의 개수
            int[] cars = new int[N]; // 자동차 번호 배열
            for (int j = 0; j < N; j++) {
                cars[j] = scan.nextInt();
            }
            process(cars);
        }
    }
    public static void process(int[] cars) {
        // 바로 들어갈 수 있는 차들은 보내고 나머지만 남긴다.
        int i = 0;       
        while(cars[i] == (i + 1)) {
            i++;
        }
        cars = Arrays.copyOfRange(cars, i, cars.length);
        // 다음으로 들어가야할 차의 위치를 구한다.       
        int index = getIndexOfMinValue(cars);
        // 그 녀석보다 앞의 차들은 바이패스로...
        // 그 녀석보다 뒤의 차들은 원래 라인으로...       
        int[] bypass = Arrays.copyOfRange(cars, i, index);
        int[] original = Arrays.copyOfRange(cars, index + 1, cars.length);
        // 두 라인에서 순서대로 들어갈 수 있으면 YES
        // 아니라면 NO를 출력한다.
        if (isSorted(bypass) && isSorted(original)) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }
    /**
        * 배열에서 최소값의 위치를 구한다.
        * @param numbers 배열
        * @return 최소값의 위치
        */
    public static int getIndexOfMinValue(int[] numbers) {
        int min = numbers[0];
        int index = 0;
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] < min) {
                min = numbers[i];
                index = i;
            }
        }
        return index;
    }
    /**
        * 오름차순으로 정렬되어 있는지 판단한다.
        * @param numbers 정수 배열
        * @return 오름차순으로 정렬되어 있으면 YES, 아니면 NO
        */
    public static boolean isSorted(int[] numbers) {
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) {
                return false;
            }
        }
        return true;
    }
}

Comment

문제를 잘못 이해해 bypass에 차가 한 대만 들어간다고 생각해버렸다. 다시 수정하여 풀었다. 정렬을 이용하여 풀어보았다. 하지만 Queue를 이용해서 풀면 좋을 듯한 문제인듯 ㅋㅋ

Share Comments