[Hackerrank] [Medium] New Year Chaos

https://www.hackerrank.com/challenges/new-year-chaos/forum

Discussion on New Year Chaos Challenge

풀이

• Input : 1 이상의 정수로 구성된 list
• 순번이 뒤에 있는 사람이 바로 앞 사람에게 뇌물을 줌으로써 순서를 바꿀 수 있음.
• 한 사람이 사용할 수 있는 최대 뇌물은 2. -> 한 숫자마다 최대 2번 swapping
• 모든 경우의 수를 구하거나, 리스트 값을 덮어씌우거나 새로운 저장공간을 할당해 현황을 매번 저장할 필요 없음.
• 뇌물을 받은 개수만 counting해서 풀어도 됨.

def minimumBribes(q):
    move = 0
    # enumerate로 시작하는 index와 q의 값과 같게 해주기 위해 1씩 빼줌
    Q = [i-1 for i in q]
    for idx, person in enumerate(Q):
        # index와 val의 차이가 2보다 크면 최대 swapping 수 2를 초과.
        if person - idx > 2:
            print("Too chaotic")
            return
        # person이 얼마나 뇌물을 받았는지 검사.
        # 최대 뇌물 수가 2이기 때문에, person보다 큰 값이 바로 앞까지만 올 수 있음(두칸 앞이면 Too chaotic)
        for j in range(max(person-1,0), idx):
            if Q[j] > person:
                move += 1
    print(move)