Pairs of Songs With Total Durations Divisible by 60

노래 리스트가 주어지고 i 번째 노래의 길이는 time[i] 초다.

노래 한 쌍의 전체 길이가 60으로 나누어지는 모든 쌍의 개수를 구하자. 좀더 정확하게는, 한 쌍의 노래 인덱스 i, j에 대해서 i < j 이고 (time[i] + time[j]) % 60 == 0인 쌍의 개수를 구하자.

대관절 이게 머선 말이냐

이 문제를 처음 읽었을 때는 언뜻 이해가 가지 않았다. 왜냐하면 이때까지 풀었던 문제는 늘 정답을 한 큐에 풀 수 있는 어떤 알고리즘이 있었고, 대개 이 알고리즘을 적당히 변형하면 되겠거니 하는 감이 있었기 때문이다 (e.g. DFS, Stack, …).

근데 이 문제는 그런 감이 전혀 오질 않았다. 아마 내 수련이 부족한 탓이겠다. 이럴 땐 당황하지 말고 일단 문제가 요구하는 조건이 뭔지 구체적인 예제로 차근차근 파악해 나가야 한다.

예시 1

time = [30, 20 ,150, 100, 40]이 주어졌다고 하자. 이때 답은 3이 되는데,

(time[0], time[2]): 합이 180초가 되고 60으로 나누어 떨어진다.
(time[1], time[3]): 합이 120초가 되고 이하동문.
(time[1], time[4]): 합이 60초가 되고 이하동문.

뭔가 예시를 보니 감이 잡힐 것 같기도 하다.

Brute Force

일단 예시를 보니 Brute Force는 금방 떠올랐다.

def num_pairs_of_songs(time):
    answer = 0
    n = len(time)
    for i in range(n):
        for j in range(i+1, n):
            if (time[i] + time[j]) % 60 == 0:
                answer += 1

    return answer

조건에 맞게 i < j를 유지하기 위해서 안쪽 루프에는 range(i+1, n) 범위를 돌아야 한다.

이렇게 하면 대충 O(n^2) 이라는 끔찍한 복잡도가 나온다. 문제에서 time의 크기가 최대 6 * 10^4까지 가능하기 때문에 아주 큰 입력에 대해서는 끔찍하게 느릴 게 분명하다.

60으로 나눈 나머지를 저장해두기

모든 쌍에 대해서 일일이 검사하지 말고, 한 큐에 “지금 나랑 쌍이 될 수 있는 애가 있는지?”를 알 수 있으면 복잡도를 줄일 수 있겠다.

여기서 조건은 60으로 나누어 떨어지는지, 즉 모듈러 연산의 결과가 0인지를 판단하는 것이다. 모듈러 연산의 특징으로 인해 모든 시간에 모듈러를 미리 해둬도, 나중에 합해서 모듈러를 하면 똑같은 결과가 나온다. 이 성질을 이용하면, i 번째 노래의 모듈러 연산 결과(60으로 나눈 나머지)를 미리 저장해두고, “나랑 더해서 60(혹은 0) 이 되는 친구가 있나?”를 빠르게 살펴볼 수 있을 것 같다.

좀더 구체적으로 생각해보면 다음과 같다. i < j에 대해서,

time[i] % 60 == 0 이면, time[j] % 60 == 0이어야 한다.
time[i] % 60 > 0 이면, time[j] % 60 == (60 - (time[i] % 60)) 이어야 한다.

time[i] % 60의 인덱스만 구해보면 다음 상황과 같다.

time: [30, 20, 150, 90, 40]

remainders: {
  20: [1],
  30: [0, 2, 3],
  40: [3, 4],
}

여기서 어떻게 우리가 원하는 답인 i<j인 쌍의 개수를 구할 수 있을까?

원소 순서대로 time을 훑으면서 time[t % 60]의 개수를 1씩 증가시킨다고 해보자. 그러면 위의 예시에서, i = 3 일 때의 상황은 다음과 같다.

i:     0 , 1 , 2  , 3 , 4
time: [30, 20, 150, 90, 40]
remainders: {
  20: 1,
  30: 2,
  40: 0
}

time[3] = 90 이므로 90 % 60 = 30 이다. 따라서, 조건에 맞는 친구는 나머지다 60 - 30 = 30 이어야 하고 이 개수는 remainders[30] = 2 이다. 이때, time을 순서대로 훑으면서 remainders를 업데이트 하고 있으므로, 이 시점에 담긴 remainders[30] = 2는 현재 인덱스인 3보다 작은 인덱스 이면서 조건을 만족하는 아이들의 개수이다. 점점 우리가 원하는 그림에 다가가고 있다.

여기서 좀더 들어가서 그럼 이 remainders 값으로 부터 쌍의 개수를 어떻게 구할 수 있을지 생각해보자. 어떤 인덱스 i에 대해서 time[i] % 60 > 0이고, time[60 - (time[i] % 60)] = f 라고 해보자. 즉, i보다 작은 인덱스를 가지면서 조건(쌍을 만들고 합친 다음 60으로 나누어 떨어질 수 있는)을 만족하는 원소의 개수가 f개이다. 그럼 이때 가능한 쌍의 개수는 몇 개일까? f개 각각에 대해서 현재 원소 i와 쌍을 만들 수 있므로 f개가 된다. 따라서, 이 값을 곧바로 누적할 수 있다.

그리고 이렇게 정답 개수를 누적한 이후에, 현재 인덱스가 60으로 나눠 떨어지는 개수를 업데이트 하면 된다. 이를 코드로 작성하면 다음과 같다.

from collections import defaultdict
def num_pairs_of_songs(time):
    # cache modulo results
    remainders = defaultdict(int)
    answer = 0
    for t in time:
        if t % 60 == 0:
            answer += remainders[0]
        else:
            answer += remainders[60 - (t % 60)]

        remainders[t % 60] += 1

    return answer

앞의 조건에서 처럼 t % 60 == 0인 경우와 그렇지 않은 경우를 나누어 생각했다.
answer의 개수는 조건을 만족할 수 있는 remainders의 개수를 곧바로 누적하면 된다.
answer를 누적한 이후에 현재 원소의 remainders를 업데이트 해준다.