문제 요약
주어진 numbers를 가지고 만들 수 있는 모든 조합 중, 소수에 해당하는 조합의 개수를 return하는 문제이다.
// 예시 및 설명// numbers : "17"
// => [1, 7]으로는 소수 [7, 17, 71]을 만들 수 있으므로 3을 return한다.// numbers : "011"
// => [0, 1, 1]으로는 소수 [11, 101]을 만들 수 있으므로 2를 return한다.
최종 작성 코드
중요하다고 생각되는 키 포인트를 중심으로 내용을 정리하였다.
키 포인트
- 완전 탐색(순열)로 가능한 모든 조합 찾기.
- 소수 찾기 알고리즘(소수판별법)으로 소수 판별하기.
- 중복된 조합이 존재할 경우 카운트에 포함하지 않도록 하기. (Set)
1. 완전 탐색(순열)로 가능한 모든 조합 찾기.
완전 탐색
전체 요소를 일일이 순회하여 가능한 모든 경우의 수를 도출하는 것
말 그대로 모든 요소들을 하나하나 확인해 가능한 조합들을 전부 찾아내는 방법이다. 완전 탐색을 수행할 수 있는 방법에는 <브루트 포스, 비트 마스트, 백 트래킹, 순열 등> 여러 가지가 있는데, 여기서는 재귀 함수를 통해 순열을 구하는 것으로 완전 탐색 문제를 해결하였다.
어떻게 하면 순열로 완전 탐색을 수행할 수 있을까?
순열의 원리를 이미지로 살펴보면 다음과 같다.
A부터 C까지 순차적으로 요소를 스왑하는데, 요소를 스왑할 때마다 고정(fixed)시킨 후 남은 요소들 역시 스왑 및 고정(fixed)하는 과정을 반복한다.
이를 고정되지 않은 요소가 하나 남을 때 까지 수행하여 조합을 도출한다. 위 그림의 경우 마지막에 나오는 여섯 가지가 얻을 수 있는 조합의 답이 된다.
처음에는 고정될 요소를 지정하고, 해당 배열을 벗어나지 않도록 하면서 남은 요소들을 어떻게 자리바꿈 해야 할지 고민 했다. 그러다 고정될 요소와 고정되지 않는 요소들을 같은 배열에 묶어 놓고 문제를 풀 필요가 없다는 것을 깨달았다.
설명
순열을 얻을 수 있는 getPermutation 함수에 요소가 담긴 배열과 비어있는 String을 인자로 제공하여 호출한다.
(아직 고정 값이 없기 때문에 빈 String 제공)
제공된 String과 배열의 i번째 요소(arr[i])를 합쳐 새로운 고정 값(newFixed)으로 지정하고, 고정된 요소(arr[i])를 splice로 배열에서 제거하여 고정되지 않은 요소들로 copyArr를 구성한다.
copyArr와 newFixed를 getPermutation의 인자로 제공해 재귀 함수를 호출하면, 실행된 재귀 함수에서는 fixed로 제공된 값에 배열의 i번째 요소(arr[i])를 가져와 붙여 newFixed를 만든 후, 붙인 요소를 배열에서 제거해준다. 이후 해당 배열과 newFixed를 다시 getPermutation의 인자로 주어 재귀 함수를 실행한다.
이를 고정되지 않은 요소가 남지 않을 때 까지 반복하여 모든 요소들을 탐색하면 만들 수 있는 모든 조합이 도출된다.
2. 소수 찾기 알고리즘(소수판별법)으로 소수 판별하기.
소수
1과 자기 자신으로만 나누어 떨어지는 1보다 큰 양의 정수.
(1과 자기 자신으로만 떨어진다 = 약수가 두 개 뿐이다)예) 19의 약수는 [1, 19] 이므로, 19는 소수이다.
약수
나눴을 때 나머지가 0이 되는 수.
예) 9의 약수는 [1, 3, 9] 이므로, 9는 소수가 아니다.
위의 정의를 그대로 적용하면 소수 여부를 쉽게 판별할 수 있다.
판별하고자 하는 수를 2부터 자신보다 작은 수로 전부 나눴을 때 약수가 하나라도 나오면 소수가 아닌 것이다.
이를 코드로 구현하면 다음과 같다.
위 과정은 당연하게 소수 여부를 판별할 수 있지만, 2부터 자신 보다 작은 수까지 전부 for문이 순회해야 한다는 단점이 있다.
예를 들어, num이 9일 경우 2부터 8까지 모든 수를 순회해야만 9가 소수인지 아닌지 판별되지만, 9를 3으로 나누어 0으로 떨어지는 시점에서 이미 소수가 아니라는 결론을 도출할 수 있다.
그렇다면 모든 수를 순회하지 않도록 과정을 최소화할 수 있는 방법은 없을까?
2부터 자신의 양의 제곱근 이하의 수까지 나누어 소수 여부를 판별할 수 있는 소수판별법을 사용하여 과정을 단축 시킬 수 있었다.
9의 경우 양의 제곱근인 3까지, 25의 경우 양의 제곱근인 5까지의 숫자로 자신을 나눴을 때 0으로 떨어지면 소수가 아니고, 떨어지지 않으면 소수라는 것이다.
JavaScript에는 양의 제곱근을 구하는 Math.sqrt() 메서드가 있으므로, 이를 이용해 for문이 순회할 범위를 좁혀주면 다음과 같은 코드가 완성된다.
3. 중복된 조합이 존재할 경우 카운트에 포함하지 않도록 하기. (Set)
<모던 JavaScript 튜토리얼>에 정리된 Set의 정의는 다음과 같다.
Set
Set(셋)은 중복을 허용하지 않는 값을 모아 놓은 특별한 컬렉션입니다.
Set에 같은 값을 추가할 경우 최종적으로 하나의 값만 저장되기 때문에 이를 이용하여 중복된 값을 추가로 저장하지 않도록 하였고, set.size로 Set에 저장된 값의 개수를 얻을 수 있었다.
Set에 대한 자세한 설명이 필요하다면 아래 링크로 방문하길 추천한다.
글을 마치며
취업을 위해 코딩테스트 문제를 풀며 알고리즘을 접하기 시작했는데, 이를 통해 알고리즘의 원리와 JavaScript의 메서드를 전보다 깊이 있게 알 수 있게 되어서 매우 다행이라고 생각한다. 향후에도 취업과 관계 없이 알고리즘 문제를 꾸준히 풀어보면 좋을 것 같다는 생각이 들었고, 현재는 많이 부족하지만 매일 꾸준히 문제를 풀어 알고리즘에 더욱 익숙해 질 수 있도록 노력할 예정이다.
읽어 주신 분들께
개발 블로그를 시작하면 좋을 것 같다는 생각을 막연하게 하고 있던 찰나에 정리하고 싶은 내용이 생겨 이렇게 첫 글을 쓰게 되었습니다. 배워가는 입장에서 쓴 글이기에 부족할 수 있고, 문제점이 있을 수 있으니 이에 대하여 지적해주시는 분이 있다면 감사히 듣고 개선할 수 있도록 하겠습니다:)
