New Year Chaos

문제

https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

 

뇌물을 주고받아 순서가 변경된 que가 주어졌을 때 몇 번 이동해야하는지를 출력.

단 아래 조건에 어긋난 que일 경우 'Too Chaotic'을 출력

 

조건

1. 바로 앞에 있는 사람한테 뇌물을 주고 앞으로 갈 수 있음
2. 한 사람 당 2명까지 뇌물을 줄 수 있음. 즉 최대 2번 앞으로 이동가능

입력 예

2   (입력 세트의 개수)

5   (큐의 길이)

2 1 5 3 4

5

2 5 1 3 4

 

출력 예
3

Too chaotic

 

첫번째 큐(2 1 5 3 4)의 경우

5가 3, 4에게 뇌물을 주고 2 번이동

2가 1에게 뇌물을 주고 1 번 이동

조건에 맞게 총 3번 이동했으므로 3을 출력

 

두번째 큐(2 5 1 3 4)의 경우

첫번째 큐에서 5가 1에게 뇌물을 주고 1번더 이동했으나 조건 2에 어긋나므로 Too Chaotic을 출력

 

제출한 코드

def minimumBribes(n, q):
    for i, j in enumerate(q):
        if (j - 1) - i > 2:
            return "Too chaotic"
    cnt = 0
    for i in range(1, n): 
        j = i
        while j > 0 and q[j-1] > q[j]: 
            q[j-1], q[j] = q[j], q[j-1]
            j -= 1
            cnt+=1
    return cnt    

풀이

1. 인덱스와 3이상 차이나는 사람이 있을 경우(2번넘게 뇌물을 준 사람이 있음) Too Chaotic 출력
2. 삽입정렬을 이용하여 이동한 횟수를 카운트하여 출력