프로그래머스 - 소수찾기(완전탐색 / C++)

 

 

문제)

 

 

 

위와 같은 문제는 주어진 numbers를 통해 만들수 있는 소수의 개수를 찾는 문제입니다.

핵심은 백트랙킹을 통한 만들수 있는 모든 소수를 만들고 중복을 제거하여 소수를 판별하는 것입니다.

 

 

문제풀이)

1. 입력받은 numbers 문자열을 문자 벡터에 저장 후 정렬 2. next_permutation() 라이브러리 함수를 이용하여 가능한 모든 순열을 생성( next_permutation를 사용하기 위해서는 정렬필요) 3. 중복 제거 4. 소수를 판하는 에라토스테네스의 체( Sieve of Eratosthenes ) 알고리즘을 이용하여 소수 판별

 

 

중복을 제거할때 unique( nums.begin(), nums.end() ) 을 사용하는데 연속된 중복된 요소를 벡터의 앞부분으로 이동시킨 후  erase( unique()리턴값, nums.end() ) 함수를 이용하여 뒤에 남아있는 중복된 요소를 지워줍니다.