👀 문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
✍🏻풀이
일단 순열을 사용하는건 알겠는데, 이걸 코드로 어떻게 구현하느냐가 너무 어려웠다.
처음에는 재귀를 사용해서 숫자를 만들어, 숫자가 붙을 때마다 newNums 벡터에 넣었는데, 숫자가 이상하게 만들어졌다..ㅠ
(코드 놔둘걸,, 다 지워버림)
아무튼 그래서 검색해보니까, algorithm 헤더에 next_permutation 함수를 사용하면 쉽게 순열을 구할 수 있다더라,,
next_permutation 함수
bool next_permutation(BidirectionIterator first, BidirectionIterator last);
-> 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool next_permutation(BidirectionIterator first, BidirectionIterator last, Compare comp);
-> 이처럼 세번째 인자에 직접 비교함수를 넣어줘도 된다.
코드
//
// Programmers_42839.cpp
// Algorithm
//
// Created by 조수민 on 2020/10/26.
// Copyright © 2020 조수민. All rights reserved.
//
// 소수 찾기(https://programmers.co.kr/learn/courses/30/lessons/42839)
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
// 소수 판별 함수
bool isPrime(int n) {
if (n == 2) // 2는 소수이다
return true;
if (n == 1) // 1은 소수가 아니다
return false;
if (n % 2 == 0) // 소수는 다 홀수이므로, 짝수는 소수가 아니다
return false;
/**
앞에서 짝수는 다 걸러줬으므로,
홀수로만 나눠본다.
n보다 작은 모든 홀수로 나눴을 때, 나누어 떨어지지 않는다면
소수이다
*/
for (int i = 3; i < n; i += 2) {
if (n % i == 0) // 나누어떨어짐 = 소수가 아니다
return false;
}
return true;
}
/**
algorithm 헤더에 있는 next_permutation 함수를 사용하면 순열을 쉽게 구할 수 있다.
*/
int solution(string numbers) {
int answer = 0;
// 순열 구하기
vector<int> newNums;
sort(numbers.begin(), numbers.end());
do {
for (int i = 1; i <= numbers.size(); i++) {
newNums.push_back(stoi(numbers.substr(0, i)));
}
} while (next_permutation(numbers.begin(), numbers.end()));
// newNums 벡터의 중복을 제거하기 위해 unique와 erase를 사용한다.
// 이 때 주의점은, sort를 한 후 사용해줘야 중복된 값이 제대로 삭제된다.
sort(newNums.begin(), newNums.end());
newNums.erase(unique(newNums.begin(), newNums.end()), newNums.end());
// 소수인지 판별, 소수가 맞으면 answer + 1
for (int i = 0; i < newNums.size(); i++) {
if (isPrime(newNums.at(i)))
answer++;
}
return answer;
}
int main() {
cout << solution("17") << endl;
return 0;
}
'숨막히는 알고말고 > 문제 풀이' 카테고리의 다른 글
[Programmers] 체육복 (0) | 2020.11.12 |
---|---|
[Programmers] 카펫 (0) | 2020.11.10 |
[Programmers] 모의고사 (0) | 2020.10.26 |
[Programmers] H-Index (0) | 2020.10.25 |
[Programmers] 가장 큰 수 (0) | 2020.10.25 |