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

https://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은 같은 숫자로 취급합니다.

풀이

해당 문제는 완전탐색 문제로 주어진 numbers의 자리 수 모두 split 하고 붙여서 하나의 숫자로 만든 후 소수 판별해야 한다.

완전 탐색의 대표적인 예인 순열, 조합과 비슷한 문제이다.

그리고 Index 숫자가 중복으로 쓰이며 안되므로 visit 배열을 통해 사용 유무를 판별하여 해결한다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;




//순열의 갯수 구하는 것!

/*
한자리 수
두자리 수 
세자리 수 
다 따로따로 구해보장!

*/
vector<char> vc; //input string 쪼갠 값의 vector
vector<char> choiceNumvc; // 선택한 Number의 vector 
vector<int> answervc; // 답 일 수 있는 Number의 vector
bool visited[8] ={false,};


/*
소수 판별 method
*/
bool prime(string chstr){
   
    int instr = stoi(chstr); // string to integer c+11에서 부터 사용가능하다.    
    if(instr < 2 ) return false;
    for(int i=2; i<instr;i++) {
        if(instr % i ==0)  {
            return false;
        }
    }
    return true;
}


/*
parameter
@count : 현재 자리 숫자
@goals : 목표 자리 숫자 (두자리 수 , 세자리 수 등)
*/

void dfs(int count, int goals) {
        
    if(count == goals) {    
        string tempstr="";
        
        for(int i=0; i < choiceNumvc.size();i++) {
            tempstr +=choiceNumvc[i]; //vector값을 +연산을 통해 string 값으로 만든다.
        }
        
        if(prime(tempstr)) {         
            answervc.push_back(stoi(tempstr));
        }
        return;
    }
    
    for(int k=0; k<vc.size();k++){    
        if(visited[k] == true) continue; //Index 숫자 사용 여부 확인
        
        visited[k] = true;
        choiceNumvc.push_back(vc[k]);       
        dfs(count+1,goals);
        visited[k] = false;
        choiceNumvc.pop_back();
    }  
    
}

int solution(string numbers) {

    /*
    17 : numbers.size()  == 2
    011 : numbers.size() == 3
    */
    for(int i=0; i<numbers.size();i++){
        vc.push_back(numbers[i]);
    }
    
    for(int j=1; j<=numbers.size();j++){
        dfs(0,j); // 여기서 j는 목표 자릿수 (최대값은 numbers의 자릿수)
    }
    
    
    sort(answervc.begin(),answervc.end()); // 중요!
    answervc.erase(unique(answervc.begin(),answervc.end()),answervc.end());
    
    
    int answer = answervc.size();
    cout<<"answer : " <<answer<<endl;
    return answer;
}

 

문제 풀다가 중복 삭제 answervc.erase(~) 이전 sort를 하지 않았는데 1,4,7,10,12 테스트 케이스가 오류가 났다.

반례로 "232"를 넣었는데 "2" ,"3", "23", "223" 4개가 나와야 하는데 5개가 나왔다. 

cout를 찍어보니 "2","3","2","23","223"이 나와서 5개였다.

2가 중복 되었다는 것인데 이 부분을 정렬하여 해결하였고 위와 같은 중복 삭제 전에는 반드시 sort 한다는 것을 배울 수 있었다. 

 

 

완료!

 

끝.