[프로그래머스] k진수에서 소수 개수 구하기(C++)

문제 URL

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

[문제 설명]

다음 문제는 정수 n과 k가 매개변수로 주어진다. 이 n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 조건에 맞는 소수의 개수를 return 하는 문제이다. 

 

주어진 조건

 

 

[문제 풀이]

문제의 조건을 보면 0을 기준으로 사이에 있는 수가 존재하는데 이 숫자가 소수인지 판별하면 되었다.

따라서 문제 해결 방법은 다음과 같다.

1. 정수 n을 k진수로 바꾸기

2. 0을 기준으로 사이에 있는 숫자 구하기 (k진수의 양 끝 숫자와 0이 없는 단일 숫자도 포함)

3. 해당 숫자가 소수인지 판별하기

 

 

[어려웠던 점]

• 어려웠던 점이라기보단 잠시 망각한 점은 풀이과정 1번을 수행할 때 k진수로 바꾸어 주려면 나머지들을 반대로 읽어야 한다는 점이었다. 마지막에 코드를 맞게 작성한 것 같은데도 계속 틀렸다고 나와서 뭐가 문제지하고 천천히 코드를 다시 봤는데 문자열을 reverse 하는 것을 완전히 잊고 있었다..

 

• 그리고 테스트 케이스 1번과 11번에서 계속 aborted (core dumped 에러)가 일어났는데 알고보니 string 문자열 str과 temp를 초기화 해주지 않아서 생겼던 문제였다. 

 

• 마지막으로 테스트 케이스 1번에서 시간초과가 떠서 구글링을 해봤는데 숫자가 길어서 int가 아닌 long을 써주어야 했다.

 

 

[다른 방식]

문자열이 아니라 stack을 이용해도 문제 풀이가 가능할 것 같아 stack을 사용하여 다시 한 번 풀어보았다.

아래 코드에서 #2 확인

 

+) 구글링을 하다가 소수 판별은 에라토스테네스의 체를 사용한다는 것을 기억해냈다. 그런데 이 문제에서 에라토스테네스의 체를 사용하면 배열에 담기게 되는 수의 크기가 엄청 커지기 때문에 배열 길이 제한을 넘기게 되어 런타임 에러가 발생한다고 한다. 나는 생각이 나지 않아 단순히 나누는 방법을 사용했는데 그 덕에 쉽게 해결할 수 있었다..

---

<#1 문자열 reverse를 사용한 방법>

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

string str = "";

// 소수를 판별하는 함수
bool sosu(string num_str){
    long num = stol(num_str);
    if(num == 1)
        return false;
    for(long i=2; i*i <= num; i++){
        if(num % i == 0)
            return false;
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    
    // k진수로 변환 & string으로 변환
    while (n > 0) {
        str += to_string(n % k);
        n /= k;
    }
    
    reverse(str.begin(), str.end());
    
    // 숫자를 구해 소수 판별
    string temp = "";
    for(int i=0; i<str.size(); i++){
        if(str[i] == '0'){
            if(!temp.empty() && sosu(temp))
                answer++;
            temp = "";
        }else
            temp += str[i]; 
    }
    
    if(!temp.empty() && sosu(temp))
        answer++;
        
    
    return answer;
}

 

<#2 스택을 사용한 두 번째 방법>

#include <string>
#include <algorithm>
#include <stack>
using namespace std;

stack<string> st;
string str = "";

bool sosu(string num_str){
    long num = stol(num_str);
    if(num == 1)
        return false;
    for(long i=2; i*i <= num; i++){
        if(num % i == 0)
            return false;
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string temp = "";
    
    // k진수로 변환 & string으로 변환
    while (n > 0) {
        st.push(to_string(n % k));
        n /= k;
    }
    
    // 숫자를 구해 소수 판별
    long size = st.size();
    for(int i=0; i<size; i++){
        if(st.top() == "0"){
            st.pop();
            if(!temp.empty() && sosu(temp))
                answer++;
            temp = "";
        }else{
            temp += st.top(); 
            st.pop();
        }
    }
    
    if(!temp.empty() && sosu(temp))
        answer++;
        
    
    return answer;
}