[Hackerrank] New Year Chaos

1일 1코테 문제 분석을 목표로 하고 있고 첫 번째 문제이다.

놀이공원 롤러코스터를 타기 위해 사람들이 줄을 서 있습니다. 각 사람은 1부터 n까지 자신의 초기 위치가 적힌 스티커를 붙이고 있습니다.

• 사람들은 바로 앞에 있는 사람에게 뇌물을 주어 위치를 바꿀 수 있습니다.
• 하지만, 한 사람이 최대 2번까지만 뇌물을 줄 수 있습니다.

최종 줄이 주어졌을 때, 뇌물이 몇 번 발생했는지 계산하세요.
만약 어떤 사람이 2번 이상 뇌물을 주었다면, "Too chaotic"을 출력해야 합니다.

입력 형식

1. 첫 줄: 테스트 케이스의 수 t
2. 각 테스트 케이스는 다음과 같이 구성됩니다:
   • n: 줄에 서 있는 사람의 수.
   • q: 최종 줄의 상태 (스페이스로 구분된 정수 배열).

출력 형식

각 테스트 케이스마다:

• 뇌물 횟수를 출력하거나,
• "Too chaotic"을 출력.

예제 입력

2

5

2 1 5 3 4

5

2 5 1 3 4

예제 출력

 

3

Too chaotic

 

처음 이 문제를 보고 단순하게 코드를 작성한건 이 코드였다.

def minimumBribes(q):
    swap = 0
    for i in range(len(q) - 1):
        tmp = 0
        for j in range(i + 1, len(q)):
            if q[i] > q[j]:
                tmp += 1
                if tmp > 2:  
                    print("Too chaotic")
                    return
        swap += tmp  
    print(swap)  
    return

이대로 제출하니 11개 중 7개가 맞고 4개는 time limit exceed가 떴다. 그래서 시간을 최대한 줄여보려고 다음과 같이 코드도 바꿔보았으나 똑같은 시간 초과가 떴다.

def minimumBribes(q):
    swap = 0
    for i in range(len(q) - 1):
        tmp = 0
        for j in range(i + 1, len(q)):
            if q[i] > q[j]:
                tmp += 1
                if tmp > 2:  
                    print("Too chaotic")
                    return
        swap += tmp
        if q[i + 1:] == sorted(q[i + 1:]):
            break  
    print(swap)  
    return

그래서 결국 코드가 O(n^2)이라는 점이 문제라고 생각해 코드 구조를 아예 바꾸었다.

먼저 문제 조건을 다시 읽어보니 1~n까지의 숫자를 가지고 있다. 그러므로 만약 현재 위치가 본인 인덱스보다 3 이상 뒤에 있으면 최소 3번을 바꿔야 하니 불가능하다. 이를 이용해

for i in range(len(q)):
        if q[i] - (i + 1) > 2:
            print("Too chaotic")
            return

이 조건을 넣어준다. 

그리고 다음으로는 이제 뇌물을 몇 번 먹이는지, 그러니까 자리를 몇 번 바꾸는 지를 세어야 한다. 그래서 자연스럽게  현재 위치에서 2번만 자리를 바꿀 수 있으니, 

for j in range(max(0, i - 2), i):
            if q[j] > q[i]:
                swap += 1

코드를 이렇게 짜주면 정답이 되겠다 생각해서 제출했더니 오답이 나왔다.

그래서 왜일까 생각을 해봤는데  코드가 원래 있어야 하는 자리, 그러니까 q[i]에서 최대 앞으로 2칸까지만 교환이 가능한지 생각해 주면 된다. 그래서 코드를 다음과 같이 짜주었다.

for j in range(max(0, q[i] - 2), i):
            if q[j] > q[i]:
                swap += 1

그래서 최종 결론은 다음과 같고,

def minimumBribes(q):
    swap = 0
    for i in range(len(q)):
        if q[i] - (i + 1) > 2:
            print("Too chaotic")
            return
        for j in range(max(0, q[i] - 2), i):
            if q[j] > q[i]:
                swap += 1
    print(swap) 
    return

정답처리 되었다.