728x90
문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/42839
- 문제 -
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
17 | 3 |
011 | 2 |
- 접근 -
1. 주어진 number문자열로 만들 수 있는 모든 순열을 체크해봐야한다. 따라서 n개( 1~number.length() )의 갯수로 이루어진 순열을 다 찾아보기 위해서 반복문 안에 재귀함수를 돌렸다.
2. 011인 경우에 1,01,10 등 중복되는 순열이 만들어진다. 따라서 set 자료구조(중복을제거 하는 특징)를 사용하였다.
- 후기 -
1. 재귀함수내에서 set에 저장하는 방법은 중복체크를 해주는 편한 방법이지만 큰 메모리가 필요하다.
- 코드 -
C++
#include <string>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
set <int> s;
vector<int> v;
bool check[7];
void solve(int cnt, int end, string numbers) {
if (cnt == end) {
int multi = 1;
int result = 0;
for (int i = v.size()-1; i >=0; i--) {
result += multi * v[i];
multi *= 10;
}
s.insert(result);
// 숫자로 바꿔서 넣어야한다.
return;
}
for (int k = 0; k < numbers.size(); k++) {
if (!check[k]) {
check[k] = true;
v.push_back(int(numbers[k])-'0');
solve(cnt + 1, end, numbers);
v.pop_back();
check[k] = false;
}
}
}
int solution(string numbers) {
int answer = 0;
v.clear();
for (int i = 1; i <= numbers.length(); i++) {
solve(0, i, numbers);
}
for (auto s_item : s) {
bool flag = false;
if (s_item == 0 || s_item == 1) {
continue;
}
for (int k = 2; k <= s_item / 2; k++) {
if (s_item%k == 0) {
flag = true;
break;
}
}
if (!flag) {
answer++;
}
}
return answer;
}
Python 3 (추가 업로드)
check=[]
vector=[]
set1 = set()
def isSosu(num):
sosu = True
if num ==1 or num==0:
return False
for i in range(2,int(num/2)+1,1):
if num%i==0:
sosu = False
break
return sosu
def exchange(vector):
str1 =""
for k in vector:
str1 = str1 +k
return int(str1)
def solve(numbers, cnt, end):
global check,vector,set1
if cnt == end:
num = exchange(vector)
set1.add(num)
return
for i,value in enumerate(numbers):
if check[i] == False:
check[i] = True
vector.append(value)
solve(numbers,cnt+1,end)
vector.pop()
check[i] = False
def solution(numbers):
global check,vector,set1
answer=0
for end in range(1,len(numbers)+1,1):
check = [False for i in range(0,7,1)]
vector = []
solve(numbers, 0, end)
for k in set1:
if isSosu(k):
answer+=1
return answer
728x90
'알고리즘 > 프로그래머스' 카테고리의 다른 글
프로그래머스 - H-index(level 2)//Wanna Be 컴잘알 (0) | 2019.10.17 |
---|---|
프로그래머스 - 전화번호 목록(Level 2)/Wanna Be 컴잘알 (0) | 2019.10.17 |
프로그래머스 - 조이스틱(level 2)//Wanna Be 컴잘알 (0) | 2019.10.17 |
프로그래머스 - 더 맵게(Level 2)/Wanna Be 컴잘알 (0) | 2019.10.09 |
프로그래머스 - 큰 수 만들기(Level 2)/Wanna Be 컴잘알 (0) | 2019.10.09 |