Arrays HackerRank Algorithms ‘New Year Chaos’ solution

Problem

It’s New Year’s Day and everyone’s in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by 1 from 1 at the front of the line to n at the back. Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n=8 and Person 5 bribes Person 4, the queue will look like this: 1,2,3,5,4,6,7,8. Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

Sample Input

2
5
2 1 5 3 4
5
2 5 1 3 4

Sample Output

3
Too chaotic

Solution

• 현재 정렬이 올바른 정렬인지 확인하기 위해 따로 배열을 만들지 않고 첫번째 값은 1이 되어야 하고, 두번째 값은 2가 되어야 하므로 i는 0부터 시작한다는 것을 고려해 i+1과 비교했다. q[i] != i+!
• 지금 새치기한 사람이 이전에도 새치기 한 적이 있는지 확인하기 위해 리스트를 쓰려다가 그냥 배열을 사용했다. 배열의 인덱스가 곧 새치기한 사람을 의미하며 새치기한 횟수를 저장한다.
• 만약 새치기를 이미 두번이나 했는데 또 새치기를 했다면 Too chaotic을 출력한다. (참고로, 새치기는 앞으로 가기 위함이므로 현재 위치 i의 값이 정렬된 값이 아니라면 i번째 수는 새치기한 사람이다.)
• i번째 사람이 있을 곳이 아니긴 한데 i번째도 새치기를 언제했는지 확인하기 위해 q[i] > q[i+1]를 사용했다. i번째 사람이 뒷 사람보다 순서가 빠르면 (q[i] < q[i+1]) i번째 사람은 i+1번째 사람을 새치기 하지 않았다.
• 새치기 했다는 것이 확인되면, 순서를 바꾸어준다. 새치기 횟수를 세는 bribes 변수 값을 증가한다.
• i번째 사람이 원래 있을 곳에 있으면 모든 사람이 제대로 정렬되었는지 확인하는 match변수를 증가한다.
• 새치기 횟수를 출력한다.

Code

static void minimumBribes(int[] q) {
        int[] bribers = new int[q.length+1];
        int bribes = 0; boolean flag = true;
        
        while(flag) {
            int match = 0;
            for(int i = 0; i < q.length;) {
                if(q[i] != i+1) {
                    if(bribers[q[i]] == 2) {
                        System.out.println("Too chaotic"); return;
                    }
                    
                    if(q[i] > q[i+1]) {
                        bribes++; bribers[q[i]]++;
                        int tmp = q[i]; q[i] = q[i+1]; q[i+1] = tmp;
                    }else i++;                    
                }else {
                    match++; i++;
                }
            }
            
            if(match == q.length) flag = false;
        }
        System.out.println(bribes);
    }