[프로그래머스] 소수 찾기

소수 찾기

문제 소개

문제 소개

• 한 페이지 짜리 문제 얼마나 좋아.
• 문자열에 있는 숫자를 조합해서 나오는 수의 소수 개수를 리턴.

나의 문제 풀이

1. 소수를 판별하는 메서드.
2. 문자열에 있는 숫자를 조합하기.
3. 조합된 문자열 중, 중복 제거.

• 1은 정말 쉬워보임.
• 2는 감이 안잡힘.
• 3은 HashSet 자료구조를 활용.

IsPrime

• 처음에는 num/2 까지 순회해서 소수를 판별하는 코드를 생각했는데, 찾아보니 제곱근으로도 가능하다고 한다.

FindNumbers

• Gemini의 도움을 받으면서 완성된 코드이다.

만약 문자열이 "123" 이렇게 들어온 다면, 만들 수 있는 조합은
1, 2, 3
12, 13, 21, 23, 31, 32
123, 132, 213, 231, 312, 321
이렇게 만들 수 있다.

여기서 문제가 문자를 사용해도 되고 안해도 된다는 점이다.
그래서 길이를 제한하는 targetLength 매개변수를 구현하였다.

또한 문자열이 "112"인 경우, 만들 수 있는 조합은
1, 2
11, 12, 21
112, 121, 211
이렇게 나온다.

이 경우를 확인해보면, 같은 수(1)라도 여러 번(2개가 들어옴)오면, 중복해서 사용할 수 있다.
그래서 해당 문자를 사용했는지 여부를 판단하는 used bool 배열을 사용했다.

for문을 이용해서 사용되지 않은 문자를 판단해서 조합하였다.
그리고 소수인지 판단하고 HashSet 자료구조인 foundPrime에 추가 하였다.

solution

• foundPrimes의 길이를 리턴하여 소수의 개수를 찾아냈다.