[Algorithm] non-divisible-subset 문제 풀이

안녕하세요, 개발자 Sean입니다. 

 

재미 삼아 코딩 문제나 풀어볼까... 하고 HackerRank의 문제를 풀어보았는데요, 해결하는데 꼬박 하루가 걸려버렸네요 ㅠㅠ

 

시간 복잡도 때문에 런타임 에러가 발생해 꽤나 애를 먹다가 결국 다른 분들의 풀이를 한번 살펴봤는데 

 

풀이를 봐도 이해가 안 되는 부분이 있어 고생을 꽤나 했습니다. 

 

일단 저의 풀이는 아래와 같습니다. 

function nonDivisibleSubset(k, s) {
    // Write your code here
   const counter = new Array(k).fill(0);
   
   s.forEach((el, i) => {
       counter[el%k]++;
   })
   
   let result = 0;
   
   if (counter[0] > 0) result++;
   if (k%2 === 0 && counter[k/2] > 0) result++;
   
   for (let i = 1; i < k/2; i++) {
       result += (counter[i] > counter[k-i])? counter[i]:counter[k-i]; 
   }
    return result;
}

설명을 하자면, 

 

이 문제는 subset의 최대 '길이'를 알아내는 것에 목적이 있습니다. 따라서 굳이 모든 subset을 구할 필요가 없습니다. 그게 포인트입니다. 

 

대신 a와 b의 합이 k에 딱맞게 나누어 떨어지려면,

a를 k로 나눈 나머지와 b를 k로 나눈 나머지의 합이 k로 딱 맞게 나누어 떨어져야 한다는 점을 이용합니다. 

 

예를 들어 9과 7의 합은 16이고 k가 8이라면 이 둘은 딱 맞게 나누어 떨어집니다.

이를 아래와 같이 표현해 볼 수 있습니다.

 

9를 8로 나누면 나머지가 1입니다.

7을 8로 나누면 나머지가 7입니다. 

 

나머지 1과 7을 합하면 8이고 8은 k에 나누어 떨어지기 때문에 나누어 떨어진다고 볼 수 있는 것입니다. 

 

const counter = new Array(k).fill(0);
   
   s.forEach((el, i) => {
       counter[el%k]++;
   })

이 코드는 k의 개수만큼의 배열을 만들고 s 배열에 있는 숫자 중 k로 나눈 나머지가 동일한 숫자가 몇 개 있는지를 구하는 반복문입니다. 

 

예를 들어, k가 8이라면 처음 counter의 형태는 아래와 같을 겁니다. 

 

const counter = [0,0,0,0,0,0,0,0];

 

만약 여기서 루프 문을 거친 결과가 아래와 같다면, 

 

const counter = [1,0,2,7,3,5,0,0];

 

s 배열의 숫자들 중에서 딱 나누어 떨어지는 숫자는 1개

s 배열의 숫자들 중에서 1이 남는 숫자는 0개

s 배열의 숫자들 중에서 2가 남는 숫자는 2개

s 배열의 숫자들 중에서 3이 남는 숫자는 7개

s 배열의 숫자들 중에서 4가 남는 숫자는 3개

s 배열의 숫자들 중에서 5가 남는 숫자는 5개

s 배열의 숫자들 중에서 6이 남는 숫자는 0개

s 배열의 숫자들 중에서 7이 남는 숫자는 0개

 

라는 의미가 됩니다. 정말 신박한 접근법이 아닌가요? ㅎㅎ 

저도 다른 분들의 풀이를 보고 나서야 알게 되었습니다. 

 

k가 8이라고 한다면 3이 남는 숫자들이 만약에 5가 남는 숫자랑 더하게 된다면 어떤 일이 벌어질까요?

무조건 딱 나누어 떨어지게 되겠죠. 여기서 숫자가 어떤 숫자인지는 전혀 중요하지 않습니다. 나머지가 3과 나머지가 5가 남는 숫자는 절대로 함께 존재할 수 없게 되는 겁니다. 

 

1과 7, 2와 6 등도 마찬가지입니다. 

 

반대로 보자면 이 둘 중 하나만 선택된다면 다른 어떤 숫자와 더해지더라도 딱 나누어 떨어질 일이 없다는 것이죠. 

 

그렇다면 방법은 쉬워집니다. 3이 남는 숫자들의 개수와 5가 남는 숫자들 중에 많은걸 택하면 되겠죠?

위 예에서 3이 남는 숫자가 7개이고 5가 남는 숫자가 5개이니 3이 남는 숫자를 선택하면 더 긴 결괏값을 만들 수가 있을 겁니다. 

 

하지만 약간의 엣지 케이스 처리가 필요합니다. 

 

우선 0으로 딱 나누어 떨어지는 숫자가 1개 이상 있을 경우입니다. 예를 들어 k가 8이고 배열 s에 8, 16, 24가 있다고 가정해 보겠습니다. 

 

그렇다면 counter[0]의 값은 3이 되겠죠. 8과 16 그리고 24는 8의 배수가 아닌 어떠한 수와 더하더라도 8로 나누어 떨어지지 않을 겁니다. 하지만 8의 배수끼린 더하는 순간 나누어 떨어지게 됩니다. 따라서 결과 배열에는 8과 16 그리고 24 중 단 한 개만이 포함될 수 있다는 겁니다. 이 세 숫자 중 어떤 게 선택될지는 모르지만, 그건 전혀 중요하지 않습니다. 배열의 길이에 1이 추가된다는 것만이 중요하죠. 

 

따라서 아래와 같은 코드가 해당 부분을 처리해주는 겁니다. 

   if (counter[0] > 0) result++;

마찬가지 이유로 k가 짝수일 때는 counter[k/2]의 숫자들이 같은 처지에 놓이게 됩니다. 

 

따라서 아래와 같은 조건을 사용하는 것이고요.

   if (k%2 === 0 && counter[k/2] > 0) result++;

 

이해가 잘 되셨나요?