-
프로그래머스 고득점 kit(유형정리) - 소수찾기Algorithm/Brute Force 2023. 1. 31. 10:31728x90
코딩테스트 연습 - 소수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
"17" 3 "011" 2 예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.- 11과 011은 같은 숫자로 취급합니다.
문제 자체의 이해는 입출력 예시를 통해서 충분히 이해할 수 있을 것이다. 그럼 이제 이 문제의 관건을 생각해 보자.
1. 소수 선별(유명한 isPrime_number 알고리즘을 사용) - 에라토스테네의 체
2. 어떻게 수를 나눌 것인가?(ex) "17" -> "1", "7"
3. 어떻게 나눈 수를 한자리, 두자리, 세자리 ... 식으로 붙일 것인가?
4. 수를 모두 만들고 나서 중복을 제거 해야함(set을 사용)
이렇게 4가지의 관건이 떠오른다. 바로 떠올랐던 1번과 4번 관건의 해결법은 미리 기재했다.
2번과 3번은 어떻게 할 수 있는지 메서드가 분명 있을 것이라고 생각하여 구글링을 시도 했다.
2. 어떻게 수를 나눌 것인가? -> permutations를 사용한다!!! : 모든 순열을 표현해 주는 메서드
3. 어떻게 나눈 수를 한자리, 두자리, 세자리 ... 식으로 붙일 것인가? -> permuations와 함께 " ".join을 사용하게 되면 "1", "7"의 경우 1, 7, 17, 71 과 같은 식으로 붙일 수 있다.
※ 알고리즘
1. set과 map을 사용하여 int형의 튜플을 만든다.
2. 튜플 속을 "".join, permutations를 통해서 i+1개짜리 순열을 numbers 배열 안에서 만들어 나타낸다.
3. result 변수에 set과 map을 사용하여 순열로 만들어서 조합된 모든 리스트들을 하나로 더한다. [0]이라는 의미 없는 수를 초깃값으로 설정하여 sum함수로 리스트들을 합친다.
4. isPrime_num() 함수는 에라토스테네스의 체를 사용한다.
5. result 변수 안에서 소수가 맞으면 count += 1 하여 return 시킨다.
import math from itertools import permutations def solution(numbers): answer = 0 count = 0 result = [] for i in range(len(numbers)): result.append(list(set(map(int, map("".join, permutations(numbers, i+1)))))) result = list(set(map(int, set(sum(result, [0]))))) for i in result: if isPrime_num(i) == True: count += 1 answer = count return answer def isPrime_num(num): if num < 2: return False for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: return False return True
set과 map을 조금 복잡하게 사용했지만 새로운 "".join과 permutations를 사용하여 순열 표현을 하고 수를 쉽게 합칠 수 있는 파이썬의 장점을 볼 수 있는 좋은 문제였다.
728x90'Algorithm > Brute Force' 카테고리의 다른 글
프로그래머스 고득점 kit(유형정리) - 모음사전 (0) 2023.02.02 프로그래머스 고득점 kit(유형정리) - 카펫 (0) 2023.02.01 프로그래머스 고득점 kit(유형정리) - 피로도 (1) 2023.02.01 프로그래머스 고득점 kit(유형정리) - 모의고사 (0) 2023.01.27 프로그래머스 고득점 kit(유형정리) - 최소직사각형 (0) 2023.01.27