23.04.17. programmers 코딩테스트 문제 풀기[5]

소수만들기 문제

문제 설명
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다.
숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예
nums, result
[1,2,3,4], 1
[1,2,7,6,4], 4

입출력 예 설명
입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.
입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

나는 이 문제에는 소수 찾기와 조합 구현 두가지가 핵심이라고 봤다.

그래서, 우선 소수를 구하는 isPrimeNumber라는 함수와, 몇개를 골라 더하는 pickSomeAndAdd라는 함수를 만들어서 구현했다. divide and conquer.

 

우선 내가 푼 코드는 아래와 같다. 설명은 코드에 주석으로 적어두었다.

function solution(nums) {

    function pickSomeAndAdd(nums, some) {
        // 빈 selector array 생성하면서, map으로 idx값을 요소로 가지도록 만들어줌
        let selector = (new Array(some).fill(0)).map((_, idx) => idx)
        // selector의 가장 앞 요소가 끝까지 갈 때 까지 (끝 = num.length - some)
        let numsArr = []
        // 초기값 합계
        numsArr.push(selector.reduce((acc, cur) => acc + nums[cur], 0))
        while (selector[0] < nums.length - some) {
            // 가장 마지막 selector를 계속 움직이면서,
            selector[some - 1] += 1
            for (let i = 0; i < selector.length; i++) {
                // 그 앞 selector가 도달할 수 있는 최대(nums.length - some + i + 1)에 도달하면,
                let comparing = nums.length - some + i + 1
                if ((selector[i] >= (comparing)) && i > 0) {
                    // 앞 selector++
                    selector[i - 1] += 1
                    // 그리고 자신포함 뒤의 모든 selector 초기화
                    for (let j = i; j < selector.length; j++) {
                        selector[j] = selector[j - 1] + 1
                    }
                    break
                }
            }
            // selector의 idx로 nums에서 idx값만 합계 계산 후 numsArr에 추가
            if (selector[some - 1] < nums.length) {
                //console.log(selector, selector.reduce((acc, cur) => acc + nums[cur], 0))
                numsArr.push(selector.reduce((acc, cur) => acc + nums[cur], 0))
            }
        }
        // 반환
        return numsArr
    }

    function isPrimeNumber(numsArr) {
        // 소수 찾기
        let primeArr = []
        for (let prime of numsArr) {
            let i = 2
            // sqrt(n)보다 작은 자연수에 대해 판단
            let sqrtN = Math.sqrt(prime)
            for (i; i < sqrtN; i++) {
                if (prime % i === 0) {
                    break
                }
            }
            // i가 sqrt(n)보다 크다면, 소수
            if (i > sqrtN) {
                primeArr.push(prime)
            }
        }
        // 중복 제거
        //primeArr = [...new Set(primeArr)]
        // primeArr의 길이(소수가 몇개인지)를 반환
        return primeArr //primeArr.length
    }

    numsArr = pickSomeAndAdd(nums, 3)
    primeArr = isPrimeNumber(numsArr)

    return primeArr.length
}

배열에서 순서와 상관없이 몇개의 조합을 추출하는 방식을 다소 거칠게 구현해봤다. 생각했던 논리는 아래와 같다. 

우선 문제는 3개를 뽑는 것으로 제한했지만, 이왕이면 몇개든 선택할 수 있는 코드를 구현해보고 싶어서 조금 더 시간이 걸렸다. 

우선 5개 중에 3를 뽑는다고 생각하고 어떻게 구현해야할지 생각했다. 배열은 index로 표현하고, 뽑는 selector라는 것을 가정하고, selector ①, ②, ③ 이 있다고 가정하면,

index	0	1	2	3	4
selector	①	②	③
	①	②		③
	①	②			③
	①		②	③
	①		②		③
	①			②	③
		①
		①	②	③
		①	②		③
			①	②	③

위와 같이 순차적으로 고를 수 있다. 

이걸 코드로 구현하면 되는데, 우선 for문으로 구현한 것이 위의 pickSomeAndAdd 함수이다.

 

구현한 방식은,

1. 뽑는 개수만큼 selector 배열 생성하고, selector 배열의 요소가 뽑는 대상인 배열의 index를 의미하도록 정의하고,

2. selector 요소에 대한 for문에서, selector의 가장 마지막 요소만 증가시키면서, 각 selector요소가 갈 수 있는 최대한에 도달했는지 판단("뽑는 대상 배열의 길이 - 뽑는 개수 + selector 배열의 index + 1" 이상이 되는 경우)하고, 만약 도달했다면 자신 앞의 selector의 값을 1 증가시키면서, 자신을 포함한 뒤의 selector를 그 뒤에 연속하도록 초기화 한다. 

3. selector의 요소를 index로 해서 뽑는 대상 배열에서 값을 찾아 합을 구한다.

4. 가장 앞 selector 요소가 도달할 수 있는 최대한에 도달하면 while문을 끝낸다.

 

단순한 논리로 구현했다.

 

재귀함수를 쓴다면 조금더 간결하지만, 가독성은 좀....안좋지만 아래와 같이 만들 수 있다.

function pickSomeAndAdd(nums, some) {
    let numsArr = []

    function selector(startIndex, current) {
        if (current.length === some) {
            numsArr.push(current.reduce((acc, cur) => acc + cur, 0))
            return
        }

        for (let i = startIndex; i < nums.length; i++) {
            current.push(nums[i])
            selector(i + 1, current)
            current.pop()
        }
    }
    selector(0, [])
    return numsArr
}

재귀함수에 for문까지 붙으니까, 더 설명하거나 일기 힘들지만 결과적으로 위 표로 요약한 계산을 재귀적으로 풀고 있는 것. selector 함수가 재귀적으로 호출되는데, some과 같아지면 합계를 구해서 numsArr에 push하고, 그 전까지는 for문을 돌면서 selector가 움직인다. 

 

첫번째 호출에서 첫번째 selector를 고정하고, 두번째 selector의 for문이 돌고, 그 다음 selector for문.... 으로 연속되면서,  selector의 current 배열의 개수가 뽑는 개수만큼이 차면 반환되면서 마지막 값을 없애고(pop) 그 다음 값을 찾고, 끝까지 찾으면 그 앞 selector의 for문의 i가 하나 증가하면서 반복하는 식인 것.