[프로그래머스 Level 2] [완전탐색] 모의고사 (C++)

안녕하세요! 코딩하는 경제학도 쏘코입니다. 즐거운 설 명절 보내셨는지 모르겠습니다. 저는 설을 맞이해서 오랜만에 누나와 매형과 놀면서 정말 푹 쉬었습니다!

이제 다시 일상으로 돌아와서 오늘은 매우 어려웠던 완전탐색의 모의고사 문제를 들고 왔습니다.

출처 : 프로그래머스 코딩테스트 연습 고득점KIT, programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이

programmers.co.kr

0. 문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

0.0. 제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

0.1. 입출력 예

numbers	return
17	3
011	2

0.2. 입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

1. 풀이 과정

사실.. 정말 어려워서 검색에 많이 의존했습니다. (그래도 사람들의 풀이를 보니 제 풀이가 굉장히 짧은 편이라 만족했습니다!)

우선 순열을 나타내기 위해서 next_permutation의 사용법을 이해해야 했습니다.

next_permutation을 쓰지 않고는 굉장히 풀기 까다로운 문제였습니다. 여기서 검색시간이 조금 소요됐네요.

순열을 사용하기 위해서 do while문을 이용해서 반복했습니다. 잘 안쓰게 되는 do while문이지만, next_permutation을 begin()부터 돌리기 위해서는 먼저 정렬 후에 첫 번째 작업을 수행한 후에 해야했기 때문에 이렇게 했습니다. 물론 그냥 처리하고 while문으로 해도 되지만 같은 코드가 2번 반복되니 이 경우에는 do while문이 훨씬 효율적입니다.

do while문 안에는 이중for문을 사용해서 나올 수 있는 조합들을 set에 넣어주었습니다.

temp = temp*10 + numbers[j] - '0'형태로 계속 돌리면 string 형태의 숫자를 int형태로 바꿔줄 수 있습니다. 이 부분은 백준 저지에 있는 C++로 큰 수 연산하기를 반복하다보니 수월했습니다. (근데 =써야하는데 += 잘못썼다가 1시간동안 헤맸습니다 ㅋㅋㅋㅋㅋ)

그리고 위에 언급했듯이 set을 사용했습니다. 이전 문제를 풀면서 set이 자동으로 정렬해주고, 중복이 없는 key를 담는다는 사실을 알고 있었기 때문에 보다 편하게 코드를 짤 수 있었습니다.

그 다음에는 중복을 제거한 순열들을 저장한 set에서 key들을 가져와서 소수를 확인했습니다. 이 과정은 따로 isPrime라는 함수를 만들어서 해결했습니다. 0과 1은 소수가 아니기 때문에 따로 예외를 두었고, 그보다 큰 수에 대해서는 직접 나눠보면서 나머지가 발생하지 않으면(=나누어 떨어지면) false를 반환하게 만들었습니다. 어떤 수의 제곱근까지 나누었을 때 어떤 수가 나누어 떨어지지 않으면 true를 반환하게 했습니다. 즉 Prime(소수)라는 이야기가 되죠.

sqrt를 사용한 이유는 어렸을 때 어딘가에서 주워들은 '에라토스테네스의 체'와 '제곱근을 이용한 소수판별'이라는 아이디어를 이용했기 때문입니다. 간단하게 말하면 자연수 N이 소수이기 위한 필요충분조건은 N이 N제곱근보다 크지 않은 어떤 소수로 나눠지지 않는다는 것입니다.

에라토스테네스의 체에 대해 좀 더 자세하게 설명해보도록 하겠습니다.

소수는 약수로 1과 자신만을 가지는 정수인데, 모든 자연수는 소수들의 곱으로 표현할 수 있다는 것이 특징입니다.(정수론의 기본 정리입니다!)

그렇다면 어떤 수가 소수인지를 판단하기 위해서는 그 어떤 수를 소수들로 나눠보면 됩니다. 즉 2로 나눠보고, 3으로 나눠보고, 5로 나눠보고, ... 하는 과정이 필요합니다. 이것이 체에 거르는 과정과 유사하다고 해서 불린 이름이 바로 에라토스테네스의 체입니다. 위 코드에서는 코드의 간결화를 위해 소수만 나누지는 않았지만 결국 모든 수가 소수의 곱으로 이루어져있기 때문에 같은 원리라고 볼 수 있습니다. (따로 소수만 구해놓을 수 있다면 그게 훨씬 효율적이겠죠!)

이 과정에서 A = a*b라고 가정하면 a와 b는 모두 제곱근 A보다 클 수 없습니다.

보다 직관적으로 확인하기 위해서 12를 예로 들어봅시다. 12는 소수가 아닙니다. 1, 2, 3, 4, 6, 12로 나누어떨어지기 때문입니다. 이 약수들은 (1, 12) (2, 6) (3, 4)로 나눌 수 있습니다. 약수를 절반만 구해도 나머지 약수는 자동으로 구해집니다. 이번에는 49를 예로 들어봅시다. 1,7,49로 나누어 떨어집니다. (1, 49) (7, 7)로 나눌 수 있습니다. 편의상 7을 두번 적었으나, 결국 49의 제곱근인 7까지만 나눠보면 나머지는 굳이 계산하지 않아도 자동으로 구할 수 있습니다. 제곱근보다 큰 수로 나누었을 때 나누어 떨어지는 경우는 이미 제곱근보다 작은 수를 나누었을 때 나누어 떨어지는 경우에서 발견할 수 있기 때문이죠. 이 것이 sqrt를 사용해서 소수를 구한 이유입니다.

(소수를 구하는 알고리즘을 보다 잘 이해하려고 여러 자료와 문헌들을 찾아서 최대한 쉽게 풀어서 설명해보았습니다. 이해가 가지 않는다면 댓글을 남겨주세요!)

소수를 확인하는 과정은 set에 있는 자료들을 isPrime에 넣는 방식으로 만들었습니다. 이를 위해 for문과 iteration을 이용해서 set 안의 모든 key들의 소수 여부를 판단한 후에 소수라면 answer을 1 증가시키는 방식으로 만들었습니다.

2. 소스 코드

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

bool isPrime(int a){
    if (a == 0 || a == 1) // 신기하게 || 대신 영어로 or쳐도 된다. 검색해보니 C++17에 추가된듯?? C에서는 불가능!!
        return false;
    for (int i = 2; i <= sqrt(a); ++i){
        if (a % i == 0)
            return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    set<int> s;
    
    // nP1, nP2, ... nPi까지 모두 확인해야 한다
    // 1. next_permutation을 쓰기 위해 먼저 정렬한다.
    sort(numbers.begin(), numbers.end());
    // 2. do while문으로 값을 받아서 set에 저장한다. - set이라 알아서 중복 제거
    do{
       for(int i = 0; i < numbers.size(); ++i){
           int temp = 0;
           for (int j = 0; j <= i; ++j){
               temp = temp*10 + numbers[j] - '0';
               s.insert(temp);
           }
       } 
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    // 3. 소수 확인
    for (auto it = s.begin(); it != s.end(); ++it){
        if(isPrime(*it))
            ++answer;
    }           
    
    return answer;
}

3. 후기

사소한 실수들 때문에 꽤 오래 걸렸습니다. isPrime 함수에서 ||(or) 대신 &&(and)를 넣는 멍청한(?) 짓을 하기도 했고, = 대신 +=를 쓰는 실수를 하기도 했습니다. sqrt 앞에 <=에서 =를 빼먹는 실수도 했구요. 사소한 실수들이 무럭무럭 자라 수많은 오류를 발생시켰습니다.

~~너무 안풀려서 visual studio의 도움을 받은 것은 비밀.. main함수에서 출력하는 것이 얼마나 행복한 일인지(?)~~

이번 문제를 통해 많이 겸손해졌습니다. 그리고 프로그래밍이 아닌 수학에 대한 관심이 조금 생겼습니다. 소수를 구하는 알고리즘을 더 잘 이해하기 위해서 정수론을 찾아보는데 참 어려우면서도 신기하네요! 이건 긍정적인 효과인가요 XD