프로그래머스 - 소수 찾기 (레벨2, swift)

문제 출처
programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

    - numbers는 길이 1 이상 7 이하인 문자열입니다.

    - numbers는 0~9까지 숫자만으로 이루어져 있습니다.

    - 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

입출력 예

numbers	return
17	3
011	2

 

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

  - 11과 011은 같은 숫자로 취급합니다.

 

 

 

✨문제풀이

어렵다ㅠㅠ 순열을 공부하지 않은 상태에서 풀면 너무 어렵다ㅠㅠ 

 

 1) 만들 수 있는 모든 숫자 조합을 만들고

 2) 해당 숫자가 소수인지 파악하면 된다.

 

소수 찾기 알고리즘은 level 1에서 이미 풀었기 때문에 어렵지 않았다.

문제는 주어진 숫자들로 가능한 모든 숫자 조합을 만드는 것인데 이건 순열 알고리즘을 이용하면 된다.

거의 반나절 삽질하다 결국 찾아봤다ㅠㅠ

 

순열 알고리즘은 여러 방법이 있는데 난 DFS와 check list를 사용하는 방법을 이용했다.

www.youtube.com/watch?v=6E69_ddpBwU

이 유튜브 동영상을 참고했다. 동영상에서 설명한 파이선 코드를 조금 수정하여 사용하였다.

 

순열에 대한 자세한 설명은 동영상을 보면되고 원리를 간단히 설명하자면

숫자를 하나씩 고르면서 고른 숫자에는 체크를 해주고 체크하지 않은 나머지 숫자들을 추가해서 조합을 만드는 식이다.

이때 하나의 숫자가 만들어지면 소수인지 바로 체크하고 소수인 경우 정답 배열에 담아준다. 

정답 배열에 담아줄때는 반드시 해당 숫자가 정답 배열에 있는지 확인하고 담아줘야 한다.

주어진 numbers에 동일한 숫자가 2개 이상 있을 경우 다른 순서 조합으로 같은 숫자가 만들어 질 수 있으므로 중복되어 담길 수 있다. 꼭 체크하고 담아줘야 한다.

 

숫자 조합을 만드는 DFS 함수에 사용된 파라미터는 다음 과 같다.

  depth: 지금까지 만들어진 숫자의 자리 수(0부터 시작해서 1씩 더해가다 count가 되면 숫자가 완성된다)

  string: 선택된 숫자

  count: 만들 숫자의 자리 수