[Interview Preparation Kit] Array-3

Problem

It is New Year's Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from 1 to n. Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others.

Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print Too chaotic.

My solution 1

def minimumBribes(q):
    bribes = 0
    for i in range(len(q), 0, -1):
        find_i = q.index(i)
        change_i = (i-1) - q.index(i) 
        if change_i > 2:
            print('Too chaotic')
            return 'Too chaotic'
        q_sub = sorted(q[find_i:])
        if len(q_sub) >= 2 and i > q_sub[1]:
            bribes += 2
        elif i > q_sub[0]:
            bribes += 1
        else:
            pass
    print(bribes)
    return bribes

Timeout

최대한 코드를 간략하게 해도, 10개 케이스 중 4개가 타임 아웃이 떠서 통과가 안된다. 위의 코드의 시간 복잡도는 O(N2)이다.

이 문제에서는 시간 복잡도를 고려하기 위해, 주어지는 배열의 크기로 몇 개의 테스트 케이스를 가지며 채점을 하고 있다. 나열된 수의 개수 n이 103 이하인 경우에 대해서만 해결로는 60%의 점수만을 얻을 수 있고, 나머지 40%의 점수를 더 얻기 위해선 n의 크기가 105 인 경우까지 모두 정해진 시간 내에 해결할 수 있어야 한다.
그래서 시간복잡도를 고려하여 dynamic programming 기법을 활용해야 할 것 같다.

How?

def minimumBribes(q):
    bribes = 0
    mins = [sys.maxsize, sys.maxsize]
    for i, p in reversed(list(enumerate(q, 1))):
        if p - i > 2:
            print('Too chaotic')
            return 'Too chaotic'
        elif p > mins[1]:
            bribes += 2
        elif p > mins[0]:
            bribes += 1
        if p < mins[0]:
            mins = (p, mins[0])
        elif p < mins[1]:
            mins = (mins[0], p)
    print(bribes)

참조 - https://kinchi22.github.io/2019/02/20/new-year-chaos/