난 요즘 해커랭크에서 알고리즘 문제를 파이썬으로 푸는 재미에 푹 빠져있다. 파이썬의 간결함과 강력한 표준 라이브러리, 높은 생산성에 감탄하며 여러 간단한 알고리즘 문제들을 척척 해결해 나가던 중이었다. 쉬운 문제들의 해결에 익숙해지려던 찰나, 처음으로 해커랭크에서 timeout으로 인한 테스트 케이스 실패를 맞이하고야 말았다.
Problem
New Year Chaos라는 재미있는 제목을 가지고 있는 문제이다. 제목만 보면 무슨 문제인지 감이 잡히지 않을테니, 링크를 따라가 문제를 확인해보자.
문제의 개요를 간단하게 살펴보면 다음과 같다. 1부터 순차적으로 증가하는 n개의 숫자가 무작위로 나열되어 있다. 각 수는 자신의 초기 위치를 의미하는데, ‘뇌물’을 사용하여 자신이 원래 있던 자리보다 앞 자리로 이동하는 것이 가능하다. 뇌물을 주는 횟수를 최대 2번으로 제한하고, 그보다 많은 수의 뇌물이 사용된 상태를 ‘Too chaotic’으로 정의할 때, 주어진 수의 배열이 몇 번의 뇌물이 사용된 상태인지를 알아내는 문제이다.
Implementation
시간 복잡도를 고려하지 않는 알고리즘 문제는 생각할 거리가 많지 않을 확률이 높다. 이 문제에서는 시간 복잡도를 고려하기 위해, 주어지는 배열의 크기로 몇 개의 테스트 케이스를 가지며 채점을 하고 있다. 나열된 수의 개수 n이 103 이하인 경우에 대해서만 해결로는 60%의 점수만을 얻을 수 있고, 나머지 40%의 점수를 더 얻기 위해선 n의 크기가 105 인 경우까지 모두 정해진 시간 내에 해결할 수 있어야 한다.
1st try
나의 첫번째 시도는 그리 깊은 생각을 거치지 않았다.
가장 앞자리부터 탐색을 하면서, 해당 수 p가 자리수 i보다 3 이상 큰 경우는 반드시 뇌물을 3번 이상 사용했다는 것을 의미한다.
이 경우에 Too chaotic을 출력하고 함수를 종료한다.
그리고는 현재 타겟 수의 뒤로 위치하는 수들과 하나하나 비교하면서, 뒷 자리에 자신보다 작은 수의 개수만큼 뇌물의 횟수를 증가 하였다.
아래는 내가 이 문제의 답으로 제출한 첫 번째 코드이다.
1 | def minimumBribes(q): |
2 | bribes = 0 |
3 | for i, p in enumerate(q, 1): |
4 | if p - i > 2: |
5 | print('Too chaotic') |
6 | return |
7 | for j in range(i, len(q)): |
8 | if p > q[j]: |
9 | bribes += 1 |
10 | |
11 | print(bribes) |
위 코드의 시간 복잡도는 O(N2)이다. 깊은 생각 없이 짜여진 코드로써 어찌 보면 당연하게도, 11개의 테스트 케이스 중 7개만 통과하여 40점 만점에 22점의 점수만을 얻을 수 있었다.
2nd try
여기서 어떻게 하면 시간을 더 줄일 수 있을 지 고민했다. 먼저 생각한 건, “어떤 경우에 자신 보다 뒤에 있는 모든 수를 탐색하는 것을 피할 수 있을까”였다.
해당 수 p가 자리수 i보다 큰 값을 가지고 있다면 그 수는 뇌물을 준 것이 틀림없다. 그 경우엔 원래 자리와 현재 자리의 차이인 p - i가 뇌물을 준 횟수와 같아질 것이다. 이 경우에는 바로 뇌물 횟수를 세고, 다음 자리의 수로 넘어갈 수 있다.
그리고 만약 i번째에 위치하고 있는 수 보다 뒤에 위치한 수 중에 가장 작은 수가 i번째에 위치한 수보다 작은 경우가 존재한다면, 그것은 i번째 위치한 수가 뇌물을 사용했다는 것을 의미한다. 따라서 뒤쪽에 있는 모든 수들과 하나하나 값을 비교하던 로직을 그 값들의 최소값과 비교하는 로직으로 변경하였다.
1 | def minimumBribes(q): |
2 | bribes = 0 |
3 | for i, p in enumerate(q, 1): |
4 | if p - i > 2: |
5 | print('Too chaotic') |
6 | return |
7 | elif p > i: |
8 | bribes += p - i |
9 | continue |
10 | if i < len(q): |
11 | r_min = min(q[i:]) |
12 | if p > r_min: |
13 | bribes += 1 |
14 | |
15 | print(bribes) |
결과는 달라지지 않았다. 이번 시도에서도 11개의 테스트 케이스 중 7개만 통과해 동일한 점수를 얻었다.
정말로 안일한 시도였다. 아무리 몇몇 경우에서 빠르게 다음 수로 넘어갈 수 있다 하더라도, 최소값을 구하는 시간 복잡도는 O(N)이기 때문에 결국 위 로직의 시간 복잡도는 변하지 않고 O(N2)이었다.
3rd try
조금 다른 접근 방식이 필요하다고 느꼈다.
두 번째 접근에서도 언급하였듯이, 자신보다 뒤에 있는 수들 중 자신보다 작은 수가 있다는 것은 곧 그 수가 뇌물을 사용했다는 것을 의미한다.
두 번째 접근에선 현재 자리의 수 보다 뒤에 있는 수들 중의 최소값을 매번 구했지만, 매번 구할 필요가 없지 않겠는가?
답은 이러하다. 앞자리부터 순서대로 체크하지 않고, 뒷자리부터 앞으로 체크하며 최소값과의 비교만으로 최소값을 계속 갱신하면 되는 것이다.
뇌물을 줄 수 있는 횟수는 최대 2번으로 한정되어 있기 때문에, 현 자리까지의 최소값과, 두 번째로 작은 값을 저장하는 변수로 mins을 할당하였다. 그리고 파이썬 빌트인 함수인 reversed()를 이용해 역순으로 탐색한다.
이 부분에서 파이썬을 사용할 때 주의해야할 점이 있다. 간단히 리스트의 stride를 음수로 지정(
q[::-1])하여 역순으로 탐색하는 것이 가능하다. 하지만 이것은 데이터의 shallow copy를 생성하기 때문에 메모리의 낭비가 발생한다. 따라서 shallow copy를 생성하지 않는reversed()함수를 이용하는 것을 추천한다.
만약 현재 자리의 수 p가 두 최소값 모두보다 크다면, 해당 수는 뇌물을 두 번 모두 사용한 것이다. 만약 현재 수 p가 최소값 mins[0]보다는 크고, 두 번째로 작은 값 mins[1]보다는 작을 때에는 뇌물을 한 번만 쓴 것을 의미한다.
앞서 설명했듯이, 역순으로 탐색하며 변수 mins을 이용하는 것으로써 최소값의 갱신은 두 최소값과의 비교만으로 계속적으로 가능하다.
1 | def minimumBribes(q): |
2 | bribes = 0 |
3 | mins = [sys.maxsize, sys.maxsize] |
4 | |
5 | for i, p in reversed(list(enumerate(q, 1))): |
6 | if p - i > 2: |
7 | print('Too chaotic') |
8 | return |
9 | elif p > mins[1]: |
10 | bribes += 2 |
11 | elif p > mins[0]: |
12 | bribes += 1 |
13 | |
14 | if p < mins[0]: |
15 | mins = (p, mins[0]) |
16 | elif p < mins[1]: |
17 | mins = (mins[0], p) |
18 | |
19 | print(bribes) |
위의 구현으로 11개 테스트 케이스를 모두 통과하는 것이 가능했다. 모든 자리의 수를 탐색하면서, 최소값을 구하는 시간 복잡도를 O(N)에서 O(1)로 줄여 전체 시간 복잡도는 O(N)이 되었다.
뿐만 아니라 최소값을 저장하는 메모리 또한 2개의 정수 값을 저장하는 공간만이 필요하게 되므로, 공간 복잡도는 O(1)이다.