문제 이해하기
노래 목록이 하나 주어져 있고, i번째 노래의 재생 시간이 time[i]초라고 가정해 보겠습니다. 우리가 구해야 할 것은 두 노래의 재생 시간을 초 단위로 더했을 때 그 합이 60으로 나누어 떨어지는 노래 쌍의 개수입니다.
예를 들어 time 배열이 [30, 20, 150, 100, 40]이라면 정답은 3입니다. 실제로 (30, 150), (20, 100), (20, 40)이라는 세 쌍은 각각 재생 시간의 합이 180초, 120초, 60초로 모두 60으로 나누어 떨어지기 때문입니다.
해결 접근 방법
모든 노래 쌍을 일일이 확인하는 브루트 포스 방식은 O(n²)의 시간이 걸려 비효율적입니다. 대신 나머지(remainder)를 활용한 해시 맵을 사용하면 한 번의 순회만으로 문제를 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 두 수 a와 b의 합이 60으로 나누어 떨어지려면, 각 수를 60으로 나눈 나머지의 합 역시 60으로 나누어 떨어져야 합니다. 따라서 현재 노래의 나머지가 r이라면, 지금까지 등장한 노래 중 나머지가 (60 − r) mod 60인 노래들과 짝을 이룰 수 있습니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 나머지 값을 저장할 딕셔너리 rem을 준비하고, 정답 변수 ans를 0으로 초기화합니다.
- time 배열의 모든 요소 i에 대해 아래 작업을 수행합니다.
- i를 60으로 나눈 나머지가 0이면서 rem에 키 0이 존재하면, ans에 rem[0]을 더합니다.
- 그렇지 않고 rem에 60 − (i mod 60)이 존재하면, ans에 rem[60 − (i mod 60)]을 더합니다.
- rem에 i mod 60이 이미 있다면 해당 값을 1 증가시키고,
- 없다면 rem[i mod 60]을 1로 설정합니다.
- 순회가 끝나면 ans를 반환합니다.
예제 코드
아래 파이썬 구현 예제를 통해 동작 과정을 더 쉽게 이해할 수 있습니다.
class Solution(object):
def numPairsDivisibleBy60(self, time):
ans = 0
remainder = {}
for i in time:
if i % 60 == 0 and 0 in remainder:
ans += remainder[0]
elif 60 - (i%60) in remainder:
ans += remainder[60 - (i%60)]
if i % 60 in remainder:
remainder[i%60]+=1
else:
remainder[i%60]=1
return ans
ob1 = Solution()
print(ob1.numPairsDivisibleBy60([30,20,150,100,40]))
입력
[30,20,150,100,40]
출력
3
복잡도 분석
시간 복잡도: 배열을 한 번만 순회하므로 O(n)입니다. n은 노래의 개수입니다.
공간 복잡도: 나머지 값은 최대 0부터 59까지 60종류뿐이므로, 딕셔너리 크기는 O(min(n, 60)), 즉 사실상 O(1)로 볼 수 있습니다.