프로그래머스 42839(소수찾기)

Sangwon Shin·2021년 9월 6일

ps 프로그래머스

프로그래머스

목록 보기

1/4

📜 문제

문제링크
백트랙킹 문제는 항상 헷갈린다.. 진짜 문제 많이 풀어봐야 겠다.

📖 풀이

사실 프로그래머스에서 문제를 많이 풀어보지 않아서, 메모리 제한이나 시간 제한이 명시되어 있지않아 풀이를 어떤 방향으로 설정해야 할지 어려웠다.

공간복잡도

1) numbers 를 저장하는 vector
2) 숫자들을 조합해서 만들 수 있는 수를 저장할 vector
3) numbers 사용 여부를 저장할 array

사실 문제에서 numbers의 길이가 1이상 7이하라고 명시되어 있기 때문에 메모리 제한을 걱정할 필요는 없을것 같다.

시간복잡도

1) O(nPk) [ k=1~N ]
2) 소수판별 O(sqrt(K))

🖥 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool isused[9];//현재 인덱스 사용여부
string number;//백트래킹 중 temp 변수
vector <int> answers;//모든 소수 일단 저장하기 위한 vector

//소수를 판별하기 위한 알고리즘
bool isPrime(int num){
    
    if(num <= 1)return false;
    for(int i = 2; i*i <= num; i++){
        if(num % i ==0)return false;
    }
    return true;
}


void func(string numbers, int size, int n){
    if(n == size){
        int check_number = stoi(number);
        if(isPrime(check_number))
            answers.push_back(check_number);
        return;
    }
    
    for(int i = 0; i < numbers.size(); i++){
        if(isused[i])continue;
        number += numbers[i];
        isused[i] = 1;
        func(numbers, size, n+1);
        number.pop_back();
        isused[i] = 0;
    }
}

int solution(string numbers) {
    for(int i =1; i <= numbers.size(); i++)
        func(numbers, i, 0);
    
    //if(answers.empty())return 0;
    int answer = 1;
    sort(answers.begin(), answers.end());
    int pre_value = answers[0];
    for(int i =1; i < answers.size(); i++){
        if(answers[i] == pre_value)continue;
        pre_value = answers[i];
        answer++;
    }
    
    return answer;
}

🔨 피드백

문제를 처음 보고 크게 두 가지 부분을 어떻게 구현할지 고민했다.

주어진 숫자 종이로 만들 수 있는 모든수의 조합을 어떻게 구현할 것인가?
중복을 어떻게 제거할 것인가?

첫번째의 경우, 백트랙킹을 이용했다.
문제에서 주어진 nubmers 가 string 타입이기 때문에 계산상의 편의를 위해서 temp 변수도 string으로 선언했다.
base condition을 만족할 때, stoi를 통해서 int로 변환하고
소수일 경우, answers 벡터에 push 하도록 알고리즘을 구현했다.

void func(string numbers, int size, int n){
    if(n == size){
        int check_number = stoi(number);
        if(isPrime(check_number))
            answers.push_back(check_number);
        return;
    }
    
    for(int i = 0; i < numbers.size(); i++){
        if(isused[i])continue;
        number += numbers[i];
        isused[i] = 1;
        func(numbers, size, n+1);
        number.pop_back();
        isused[i] = 0;
    }
}

현재 size = 1 인 경우, func() 함수를 돌면서 주어진 숫자 카드를 모두 돌면서 한 자리수가 소수가 될 수 있는 경우를 모두 answers 벡터에 push 하게 된다.
이런 연산을 size를 1부터 현재 입력으로 주어진 numbers.size() 까지 반복해주면 주어진 숫자 카드로 만들수 있는 모든 소수가 numbers 에 저장된다.

하지만, 이렇게 알고리즘을 종료하게 되면 중복되는 소수도 모두 count 하는 문제가 발생한다. 이런 중복을 제거하기 위해서 answers를 정렬하고, 중복되지 않는 경우만 count 하도록 설정했다.

🤷‍♂️ 현재 프로그래머스 TC에 숫자 길이가 1인 경우가 존재하지 않는 것 같다.

int solution(string numbers) {
    for(int i =1; i <= numbers.size(); i++)
        func(numbers, i, 0);
    
    //if(answers.empty())return 0;
    int answer = 1;
    sort(answers.begin(), answers.end());
    int pre_value = answers[0];
    for(int i =1; i < answers.size(); i++){
        if(answers[i] == pre_value)continue;
        pre_value = answers[i];
        answer++;
    }
    
    return answer;
}

주석 처리를 하고 정답을 받았는데 그렇게 되면 numbers = "4" 인 경우 1을 출력하게 되어 오답을 출력하게 된다. 문제 풀때는 몰랐는데 블로그에 정리하면서 알게되었다 ㅎ

🔥 며칠전 부터 boj 19236 문제를 풀고 있는데 백트랙킹 개념이 헷갈려서 기초 문제부터 천천히 다시 풀어보고 있다.
생각이 정리되면 다시 도전해봐야겠다!!

Sangwon Shin

개발자가 되고싶어요

다음 포스트

프로그래머스 42839(소수찾기)