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

문제 및 코드

1. 생각 도출

모든 경우의 수를 구해서 해당 경우가 소수인지 판별해야 한다. 여기서 모든 경우의 수란 1, 12, 123, 13, 132, ... , 3, 31, 312, 32, 321 과 같이 각 숫자를 연결한 수를 의미한다. 모든 경우의 수를 구해야 하니 완전 탐색이 필요한 상황임을 알 수 있다.

 

그럼 어떻게 완전 탐색을 진행할 수 있을까? 배열 원소 하나를 기준으로 잡고 그 원소 뒤에 나머지 원소를 붙여 나가면서 모든 경우를 구한다. 이렇게 하면서 배열을 돌면 모든 경우의 수를 구할 수 있다. 그리고 모든 경우의 수를 set에 저장한 다음 set을 돌면서 각 원소가 소수인지 아닌지 판별한다. 경우의 수를 만들다 보면 중복 경우의 수가 나타날 수 있으니 set을 사용해서 저장한다. 

 

그럼 위의 완전 탐색을 진행하려면 어떻게 코드를 작성해야 할까... 도저히 생각이 나지 않아서 다른 코드를 참고했다. 

• 일단 주어진 숫자 string을 쪼개서 배열로 만들어 해당 배열을 돈다.
  • 배열을 돌면서 해당 배열의 원소가 맨 처음으로 오는 완전 탐색을 진행한다.
    • 해당 배열을 방문했다고 표시
    • 이전 방문에서의 원소와 해당 배열의 원소를 합한 것이 set에 있는지 확인후 없으면 넣기
    • 확인 원소가 소수인지 확인
    • for문을 돌면서 해당 배열 뒤에 다른 원소 붙이기
      • 이 for문에서 재귀적으로 함수 호출
    • 함수 마무리에 해당 배열 방문 표시 취소

2. 회고

• 완전 탐색을 해야겠다는 건 알겠는데 그걸 어떻게 구현해야 할까가 1차 관문... 그리고 그걸 재귀로 구현하는데 재귀가 이해 안 되는 부분이 많아서 2차 관문...
• 재귀는 아직도 어렵다. 손으로 직접 해 봐야 확신이 가서 재귀로 코드 바로 짜는 사람들 보면 신기하다 
• 배열 방문 표시 취소를 어디서 해야하나도 어려웠다

3. 체크

풀이 횟수	시간	정답 여부	참고 여부
2	오래...		O