mandoo.log|PS
Blog
· 2분PS

1590. Make Sum Divisible by P

#ps#leetcode

누적합을 사용하는 문제 같아 보이긴 했지만, bruteforce first 정신으로 일단 들이 박았다.

class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int[] sub;
        long total = 0;
        for(int i=0; i<n; i++){
            total += nums[i];
        }
        if (total % p == 0) return 0;

        long minLen = Long.MAX_VALUE;

        for(int i=0; i<n; i++){
            long sum = 0;
            for(int j=i; j<n; j++){
                // subArray
                sum += nums[j];
                if((total - sum) % p == 0){
                    // divisible
                    int len = j - i + 1;
                    if (len < n) { // 전체를 다 지우는 건 안됨
                        minLen = Math.min(len, minLen);
                    }
                }
            }
        }

        if(minLen == Long.MAX_VALUE) minLen = -1;
        
        return (int)minLen;
    }
}

시간 초과가 발생한다. 2중 포문으로 돌면서 하나하나 체크했는데, 이러면 n이 커져버릴 때 대비가 안된다.

힌트를 열어보니 예측했던 것처럼 prefix를 사용하라고 한다. 의아한 건 map도 쓰라는 내용이 있었다...

조금 더 효율적으로 생각할 필요가 있는데, 이제부터 체화하려고 노력해야겠다.

먼저 p로 나누어진다는 말은, 안나누어질 경우 그 나머지만큼 빼면 그 경우 나눌 수 있다는 말과 같다.

이제 이 나머지값을 key로, 그 때의 idx를 value로 하는 map을 사용하면 끝난다.

import java.util.*;

class Solution {
    public int minSubarray(int[] nums, int p) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int targetMod = (int)(totalSum % p);
        if (targetMod == 0) {
            return 0;
        }

        HashMap<Integer, Integer> modMap = new HashMap<>();
        modMap.put(0, -1);

        long currentSum = 0;
        int minLen = nums.length;

        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];
            
            int currentMod = (int)(currentSum % p);
            int neededMod = (currentMod - targetMod + p) % p;

            if (modMap.containsKey(neededMod)) {
                int pastIndex = modMap.get(neededMod);
                minLen = Math.min(minLen, i - pastIndex);
            }

            modMap.put(currentMod, i);
        }

        if (minLen == nums.length) {
            return -1;
        }
        
        return minLen;
    }
}

subArray가 0이면, 아무 숫자도 더하지않은 경우다. 인덱스가 배열에 접근하지 못하도록 (0, -1)로 생각하자. 이걸 안해주면 0번 인덱스부터 시작하는 구간을 정답으로 선택해야될 때를 처리하지 못한다.

누적합에서 prev배열 만들어 쓸 때, n+1만큼 초기화하고 시작하는 것과 동일한 처리라고 보면 된다.

그리고 문제에서 wholeArray와 같으면 -1을 반환하라고 했으니 실패조건을 미리 생각해야된다. minLength를 전체 길이로 초기화해서 그 조건을 맞춘다.

이제 배열을 앞에서부터 순회하면서, 연산을 시작한다.

지금 필요한 건? 현재까지 누적합의 나머지다.

int neededMod = (currentMod - targetMod + p) % p;

이 코드가 필요한 나머지 값이다. (현재 나머지 - 이전에 출현한 나머지) == 목표 나머지이고, 목표 나머지는 아까 처음 구했으니 이전에 출현한 나머지가 곧 목표 - 현재 나머지다.

음수가 뜨지않게 p를 더해 나머지를 구해주는 스킬을 쓰고, 이게 이제 map에 존재한다면, minLen 값을 갱신하면 된다.

map에 없으면 그냥 현재 나머지와 그 위치를 저장하면 된다.

익숙하게 사용하던 prev[i] - prev[j] 의 형태가 needMod, currentMod 형태로 나온 것 뿐이다.

아이디어만 살짝 뒤틀린 문제인데 체감 난이도가 많이 높아졌다.

Share:

Comments