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

문제

https://programmers.co.kr/learn/courses/30/lessons/42839

필요 지식

1. 순열(permutation) 구현 (nPn 말고도 nPr도 구현)
2. 소수 판별 - 제곱근까지만 검사
1. 제곱근 : <cmath>의 sqrt사용
3. set,vector개념
1. set : 중복제거
2. vector : 중복 존재

해결 방법

순서

1. 순열 사용 : 주어진 string에서 모든 가능한 수의 경우의 수 구함 ->int로 변환 후 set에 저장
• "011"의 경우, 2개의 수 중 1개를 택했을 때 나오는 경우의 수, 2개를 택했을 때 나오는 경우의 수로 나뉜다.
• 즉, 3P1 + 3P2 +3P3 (P : permutation, nPr : n개중 r개를 택했을 때 나오는 경우의 수)
• 3P1 : "011"에서 1개를 뽑을 때 가능한 경우의 수 - 0,1,1 이지만, set에 저장하므로 {0,1}저장
• 3P2 : "011"에서 2개를 뽑을 때 가능한 경우의 수 - "01","10","11"가능, set에 저장할 때에는 int로 바꾸므로, (1,10,11)이렇게 저장하지만, 3P1의 경우와 중복되는 것을 제외하면 전체 set에 있는 것 : {0,1,10,11}
• 3P3 : "011"에서 3개를 뽑을 때 가능한 경우의 수 - "011","101","110"가능, set에 저장할 때에는 int로 바꾸므로, (11,101,110)저장, but 위의 경우와 중복제거되어 전체 set에 저장되어 있는 것 : {0,1,10,11,101,110}
2. 소수 판별 : set(주어진 string에서 모든 가능한 경우 수들의 모임)안에 있는 수가 소수인지 판별
• 주어진 수의 제곱근까지만 검사

코드

효율

다른 코드와 비교 분석 1

다른 사람들의 코드를 보니, 에라토스테네스의 체(참고 : 에라토스테네스 체 사용 코드)를 사용하여 주어진 수까지 소수인 수를 먼저 구하고 난 뒤, 걸러진 수와 모든 가능한 경우의 수를 비교하는 코드들이 있었다. 나와는 순서를 달리한 셈이다.

(순서 : 소수 목록 구하기(에라토스테네스 체 이용) -> 주어진 string 가능한 수와 비교)

그 방법을 보고 나니, 내 코드를 조금 수정해도 될 것 같았다. 순열을 사용하여 모든 경우의 수를 구하되(set으로 저장), 소수 판별의 경우 각각의 수에 대하여 구하지 않고, 먼저 에라토스테네스의 체로 거른 뒤, set으로 저장하고, 두 set의 intersection을 구하는 것이다. 그 방법이 각각의 수가 소수인지 판별하는 것보다 더 나을 것 같다는 생각이 들었다. 

적용 코드 : set intersection위해서 unordered_map이용

효율 : not good 

에라토스테네스의 체를 사용하는 과정에서 생긴 문제인걸까? 에라토스테네스의 체를 사용하 때에는 엄청나게 큰 수가 들어왔을 때 그 수 전체에 대하여 소수를 구해야 해서 시간 복잡도가 O(NlogN)이다. 처음 코드처럼 제곱근을 사용한 경우, 처음부터 끝까지 소수인 것을 판별하자면 O(N√N)이지만, 실제로는 처음부터 끝까지 구할 필요없이, 순열로 걸러진 것(N에 훨씬 못미침, 상수라고 볼 수 있지 않을까?)만 확인하면 되므로, 만약 순열로 걸러진 것의 수를 상수라고 한다면 O(√N)이라고 볼 수 있다. 따라서 에라토스테네스의 체보다 더 효율이 좋게 되는 것이다. (이건 제 생각이고 이견이 있다면 메일로 남겨주세요.) 

그래서 결론은 처음 코드의 효율이 더 좋다는 것이다.

다른 코드와 비교 분석 2

permutation으로 구한 사람들 중에 나와 코드가 다른 사람들이 있어서 보았더니, algorithm library에 있는 next_permutaion으로도 구현하였다. 다음에 순열을 구할 때 이 함수를 이용해보도록 해야겠다.