Problem From. https://leetcode.com/problems/continuous-subarray-sum/
오늘 문제는 상당히 헷갈리는 문제였다.
처음에는 그냥 간단하게 생각해서 for 문 2개를 돌려서 O(n^2) 의 시간복잡도를 가지는 풀이를 썼지만 역시나 시간초과로 통과하지 못하고, O(n) 의 시간복잡도를 가지는 방법을 고민하게 되었다.
수학의 나머지를 이용하면 풀 수 있는 문제로,
리스트를 처음부터 하나씩 더해가면서 k 로 나누어 나머지와 인덱스를 구해둔다.
그리고 그 나머지가 같은 수가 나오면 그 사이에 있는 리스트가 continuous subarray 가 되는 것이다.
예를 들어 [5, 3, 7, 2, 3, 8, 9] 리스트에서 합이 6의 배수이면서 길이가 2 이상인 continuous subarray 를 찾는다고 쳤을때,
처음 5+3 = 8 이고, 8 % 6 = 2 가 된다. 이때 인덱스는 1
다음 8+7 = 15 이고, 15 % 6 = 3 이 된다. 이때 인덱스는 2
다음 15+2 = 17 이고, 17 % 6 = 5 가 된다. 이때 인덱스는 3
다음 17+3 = 20 이고, 20 % 6 = 2 가 된다. 이때 인덱스는 4
나머지가 2로 같고 인덱스가 1~4 이므로 continuous subarray 는 [3, 7, 2] 가 된다.
이런식으로 for 문을 한번만 쓰게 만들어 O(n) 의 풀이가 가능해진다.
class Solution {
fun checkSubarraySum(nums: IntArray, k: Int): Boolean {
val map = hashMapOf(0 to -1)
var sum = 0
for(i in 0 until nums.size) {
sum += nums[i]
if(map.containsKey(sum % k)){
if(i - map[sum % k]!! > 1) return true
}else {
map[sum % k] = i
}
}
return false
}
}참고할만한 유튜브 링크
https://www.youtube.com/watch?v=OKcrLfR-8mE&ab_channel=NeetCode
