[코테연습] 소수찾기
오늘은 완전탐색 - 소수찾기 문제를 풀었다.
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이 문제는 숫자가 주어지고, 숫자를 조합하여 만들 수 있는 숫자 중에서 '소수' 에 해당하는 숫자의 갯수를 리턴하는 문제이다.
숫자를 조합할 수 있는 알고리즘과
소수를 구하는 알고리즘을 합쳐 푸는 것으로 이해하였다.
숫자 조합은 DFS 와 Set 리스트로 해결하고,
소수를 구하는 방법은 isPrime 이라는 함수를 만들어 해결했다.
숫자 조합을 구하는 방법이 의외로 헷갈렸는데 조합의 갯수를 정의하는 r 의 변수와
숫자의 갯수를 반복할 수 있는 반복문으로 해결했다.
숫자가 1개부터 3개까지 반복해야한다면,
for (int i = 1; i <= 3; i++) {
//arr : 숫자 배열
//n : 숫자 배열의 모든 숫자의 갯수
//r : 조합 할 숫자의 갯수 ( 1, 2, 3 개 까지 )
//depth : dfs 내에서 몇번 반복했는지 확인하기위한 변수 ( depth == r 일경우 재귀탈출 )
//visited : 숫자 배열을 사용했는지 확인하기 위한 boolean 배열
//output : 재귀결과를 담을 배열
dfs(arr, n, r, depth, visited, output);
}
다음과 같이 반복문과 dfs 재귀를 통해서 숫자의 조합을 구할 수 있다.
재귀 결과 다음과 같이 중복되는 결과도 나타나는데,
m ==> 3
[0]
[1]
[1]
m ==> 3
[0][1]
[1][1]
[1][0]
[1][1]
m ==> 3
[0][1][1]
[0][1][1]
[1][0][1]
[1][1][0]
[1][0][1]
[1][1][0]
해당 숫자는 Set 리스트를 사용하여 조합의 중복을 제거하였다.
이후, isPrime 함수로 소수인지 여부를 판단한다.
isPrime 함수는 2부터 n 의 로그까지이다.
Math.sqrt 를 사용하여 로그를 구하는 이유는 반복문의 시간복잡도를 피하기 위함이다.
예를들어 17 이라는 숫자가 소수인지 판별하기 위해서는 단순 반복문으로는 2, 3, 4, ..., 16까지 반복했을때 나누어 떨어지는지 ( 17 % i == 0 ) 를 확인해야할 것이다.
하지만 Math.sqrt(17) 로 하였을때 4.xxx 라는 숫자가 나올 것이므로 2,3,4 까지만 반복하면 된다.
4,9,16 으로 나누어 떨어질 수라면
2,3,4 로 나누어 떨어질 것이므로 소수확인 시의 i 의 중복을 피하기 위해서 로그를 활용하여 사용하는 것이다.
해당 코드를 구현하면 다음과 같다.