[HackerRank] Non-Divisible Subset(Medium) by javascript

▷ 문제 : Non-Divisible Subset (Medium)

Non-Divisible Subset | HackerRank

▷ 해결 날짜 : 2022.04.19
▷ 소요 시간 : 2시간
▷ 풀이 과정 :
이 문제는 토론장의 도움을 받아 해결했으나 사실 아직까지도 제대로 이해를 못 했다...

 

일단 이 문제는 s 배열에서 두 원소의 합이 k의 배수가 아닌 것들의 개수를 구하면 되는 문제다.

시간 복잡도에 걸리지 않게 조합을 만들어 푼다기보다 개수만 세어주는 편이 좋다.

 

그렇기 때문에 나머지를 이용해서 문제를 해결해야 하는데,

임의의 숫자 k에 대해 (a + b) % k === 0의 경우는 (a % k) + (b % k) === 0 이랑 같다는 점을 알아야 한다.

 

만약 k가 5라면 나머지는 [0, 1, 2, 3, 4]가 나오게 되는데,

그래서 구현 첫 부분에 나머지를 인덱스라 정하고 k의 길이만큼 배열을 만들어 값을 넣어 주었다.

 

여기서 나누어 떨어지지 않는 집합의 최대 개수를 구해야 하기 때문에 1 이 나올 경우 4와 조합을 할 수 없다. (나머지 1과 나머지 4를 조합할 경우 결국 나머지가 0이기 때문에 조합이 불가능하다.)

그럴 경우 1과 4 중에 더 큰 집합의 개수를 선택하는 로직이 생겨난다.

 

추가적으로 나머지가 0인 배열과 짝수일 경우 (짝수일 경우 중간값과 조합을 할 수 있는 경우가 없다.)를 예외 처리해주면 된다.

 

그렇게 총 개수를 다 더한 결과를 반환해주면 문제가 해결된다.

 

▷ 구현

function nonDivisibleSubset(k, s) {
    const factorArray = Array(k).fill(0);
    for (let i = 0; i < s.length; i++) {
        factorArray[s[i] % k]++;
    }

    let size = 0;
    for (let i = 0; i < Math.floor(k/2)+1; i++) {
        if (i == 0 || k == i * 2) {
            size += (factorArray[i] != 0) ? 1 : 0;
        } else {
            size += Math.max(factorArray[i], factorArray[k - i]);
        }
    }
    return size;
}

▷ 복기 :
이런걸 도대체 어떻게 푸는지 모르겠다 하하하...