[프로그래머스/2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기

문제를 처음 읽었을땐 굉장히 쉽게 느꼈는데 실제로 구현해보니 테스트케이스 1번과 11번에서 계속 signal aborted (core dumped) 오류가 발생했다.

 

1)

정확히 어디에서 오류가 발생했는지 잘 몰랐지만 문자열을 숫자로 바꾸는 과정에서 문제가 생긴 것은 확실한 것 같았다.

코드를 살펴보며 천천히 생각해보다가 문자열을 '0'을 기준으로 분리할 때 '0'이 연속으로 나오면서 문제가 생기는 것 같다는 생각이 들었다. 빈 값을 숫자로 바꾸려고 할 때 예외 처리를 해줘야 할 것 같아서 검색해보니 stoi, stoll 함수 등은 빈 문자열이 들어왔을 때 오류를 발생시킨다고 한다.

 

2)

다음으로 발견한 오류는 n 값의 범위에 관한 것이었다. 

 

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

위 조건에서 n은 최대 1000000까지 가능하다. k가 3이라면 k진수로 변환했을 때 int 범위를 벗어날 수 있을 것 같았다. 그래서 k진수로 변환한 숫자를 담는 자료형은 long long 타입으로 선언해 주었다. 

 

3)

이 두 오류를 찾아냈는데도 1번과 11번 테스트의 오류가 해결되지 않았다. 이 부분은 검색을 통해 해결하게 되었다. 다른 사람들의 코드에서는 stoll이 자주 보이기에 이 함수가 무엇인지 검색해보다가 문자열을 long long 타입의 수로 바꿔주는 함수라는 것을 알게 되었다.

내가 작성했던 원래 코드에서는 문자를 숫자로 바꾸기 위해 stoi 함수를 사용하고 있었다. 이 함수에서 int범위를 벗어나는 큰 입력(long long)이 들어왔을 때 오류를 발생시킨 것이었다. long long 타입의 수를 고려해야 한다면 stoll 함수를 사용해야 한다.

 

4)

signal aborted (core dumped) 오류를 해결한 후에는 1번과 11번에서 시간 초과가 떴다. n으로 큰 값이 주어졌을 때 오류가 발생했을 것이기 때문에, 시간 초과가 날만한 코드는 소수를 구하는 코드라고 생각했다. 대부분 사람들이 오름차순으로 검사하도록 구현을 했는데 나는 처음에 내림차순으로 구현을 해놓았기 때문에 검사 시작 값을 인자로 주어진 값의 제곱근으로 두어 시간초과 문제를 해결했다.

 

이 문제를 풀면서 자꾸 놓치는 데이터 타입의 범위를 주의해야 한다는 것을 다시 한번 느꼈다. 

또한 문자열과 숫자를 다루는 것이 생각보다 복잡할 수 있다는 것도 알게 되었다.

stoi, to_string, stoll, getline 등의 함수 동작을 정확하게 알고 사용해야 이유 모를 오류를 피할 수 있을 것 같다.

 

+ 프로그래머스에서 코딩테스트 연습을 처음 해봤는데 값을 제대로 저장했는지, 함수 이름이 틀리지는 않았는지 확인할 수가 없어서 힘들었다. 이런 환경에서 자주 연습하는 것이 도움이 많이 될 것 같다.

 

아래는 작성한 코드이다.

#include <string>
#include <sstream>
#include <vector>
#include<cmath>
#include <algorithm>
using namespace std;

bool is_prime_num(long long n) {
	if (n == 1) return false;
	if (n == 2) return true;
	for (int i = sqrt(n); i >= 2; i--)
		if ((n % i) == 0) return false;
	return true;
}

int solution(int n, int k) {
	string k_num;
	int answer = 0;

	//k진수로 변환
	while (n > 0) {
		k_num += to_string((n % k));
		n = n / k;
	}

	//0을 구분자로 수 분리
	reverse(k_num.begin(), k_num.end());
	vector<long long> splited_num;
	string buffer;
	istringstream ss(k_num);
	while (getline(ss, buffer, '0')) {
		if (buffer.length() > 0) splited_num.push_back(stoll(buffer));
	}

	for (auto x : splited_num) {
		//x가 소수인지 판별후 소수이면 answer++
		if (is_prime_num(x)) answer++;
	}
	return answer;
}