https://programmers.co.kr/learn/courses/30/lessons/42839?language=swift
코딩테스트 연습 - 소수 찾기
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이
programmers.co.kr
주어진 수의 경우의 수를 모두 구하고, 해당 수가 소수인지 카운트하여 총 개수를 반환하면 되는 문제
즉 "소수를 찾는 것", "조합"을 구현하는 것이 주 목적인 문제이다.
조합은 이전 후보키 문제에서도 했지만, 이번에는 순서가 뒤바뀌어도 되는 조합을 구해야한다.
즉 [A,B]와 [B,A]는 다르다는 것이다. 이 때문에 조합을 구할 때에는 첫 원소만 꺼내는게 아니라 각 위치의 원소들을 기준으로 subcombination들을 구해주어 모든 조합을 찾는다.
이에 먼저 조합을 구하는 부분부터 봐보자.
func combinations(_ elements:[String], _ k: Int) -> Set<String> {
// 중복되지 않은 값들을 저장하기 위해 반환값은 Set 타입
// 1개씩 뽑고싶을 경우는 유니크한 원소들만 반환하면 된다.
if k == 1 {
return Set(elements)
}
// 1개 미만 뽑을시는 답이 없음.
if k < 1 {
return []
}
// 결과 저장을 위함
var result = Set<String>()
// 0 ~ 마지막 원소를 각각 기준으로 하는 조합들을 구해주는 과정
for i in 0..<elements.count {
// 기준이 되는 원소를 미리 저장해둔다.
let temp = elements[i]
// 배열도 미리 저장
var tempElements = elements
// 기준이 되는 원소는 배열에서 삭제
tempElements.remove(at:i)
// 기준 원소를 제외한 배열의 조합을 구하고
let subCombos = combinations(tempElements, k-1)
// 위 결과를 기반으로 기준 원소와 각각 합친 값들을 얻는다.
let subarray = subCombos.compactMap { temp + $0 }
// subcombo와 유니크한 subarray를 구하여 더해준다.
result = result.union(subCombos)
result = result.union(Set(subarray))
}
return result
}
기존의 combination을 구하는 방법과 조금 다른 방식으로 풀어져있다.
하지만 원리는 동일하니 이해하기 수월할 것 이다.
그리고 이제 소수인지 확인해주는 함수를 작성해보자.
여기서 소수를 구할 때에는 "에라토스테네스의 체"라는 알고리즘을 이용한다.
자세한 원리는 코드를 보면서 알아보자.
func isPrime(_ n: Int) -> Bool {
// 소수일 경우 true, 아니면 false
var state = true
// 0,1을 제외하고 2부터 해당 값의 배수인지 확인한다.
for i in 2..<n {
// 배수에 해당된다면 소수의 자격 충족 X
if n % i == 0 {
// false처리해주고 바로 반복문을 종료한다.
state = false
break
}
}
return state
}에라토스테네스의 체 알고리즘은 n의 배수인지 반복문을 돌며 체로 거르듯이 판단하는 것이다.
위 for문 처럼 2의 배수인지 확인하고 그 다음 3의 배수인지... n-1의 배수인지 확인하면서, 나머지 값이 0으로 떨어지게 되면 소수가 아니고, 그렇지 않을 경우 소수에 해당한다.
처음에는 2라는 체를 들고 2의 배수인 것을 모두 거르고, 쭉쭉쭉 진행되게 되는 것이다.
위 사용한 반복문의 경우 한 가지 숫자를 위한 경우이지만, 실제 어떠한 범위 내에서 소수를 찾기에는 위에 설명한 에라토스테네스의 체 알고리즘이 매우 적합하다.
건너뛰기를 매 숫자만큼 반복하다보면 모든 징검다리를 채우는 것과 같은 원리라고 봐도 될 것 같다.
이해를 위해 그림을 잠깐 보자.
1~10까지 범위 내에서 소수인 값들을 찾아내고자 한다. 이 때 순차적으로 보는 것이 아닌 배수의 값을 기준으로 보는 방법이 "에라토스테네스의 체" 알고리즘이다. (본인의 값을 제곱한 이후부터 시작해서 배수를 모두 지워준다.)
주어진 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| F | T | T | T | T | T | T | T | T | T |
2의 배수
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| F | T | T | F | T | F | T | F | T | F |
3의 배수
3 * 3은 9이므로 9에서부터 3의 배수로 진행
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| F | T | T | F | T | F | T | F | F | F |
4의 배수는 이미 다 F이니 5로 이동
5의 배수
5 * 5는 25이나 10을 넘기에 5 본인만 체크
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| F | T | T | F | T | F | T | F | F | F |
6의 배수도 이미 F이니 7의 배수로가고 8, 9, 10의 배수는 F이니 종료되며
아래의 배열을 얻을 수 있게 된다. 여기서 T에 해당하는 2,3,5,7이 소수가 되는 것이다.
최종 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| F | T | T | F | T | F | T | F | F | F |
자 이제 조합을 구하는 방법도 알았고 소수인지 확인하는 방법도 알았으니 코드 전문을 봐보자.
import Foundation
func solution(_ numbers:String) -> Int {
// 결과 개수
var cnt = 0
// 하나의 원소들로 구분해준다
let numb = numbers.map {String($0)}
// 소수는 2이상의 값들에 해당하기에 분류 및 유니크한 숫자들만 걸러냄
let combs = Set(combinations(numb,numb.count).filter { Int($0)! > 1}.map {Int($0)!})
// 해당 숫자들이 소수인지 확인하며 결과 += 1
for n in Array(combs) {
if isPrime(n) {
cnt += 1
}
}
return cnt
}
func combinations(_ elements:[String], _ k: Int) -> Set<String> {
// 중복되지 않은 값들을 저장하기 위해 반환값은 Set 타입
// 1개씩 뽑고싶을 경우는 유니크한 원소들만 반환하면 된다.
if k == 1 {
return Set(elements)
}
// 1개 미만 뽑을시는 답이 없음.
if k < 1 {
return []
}
// 결과 저장을 위함
var result = Set<String>()
// 0 ~ 마지막 원소를 각각 기준으로 하는 조합들을 구해주는 과정
for i in 0..<elements.count {
// 기준이 되는 원소를 미리 저장해둔다.
let temp = elements[i]
// 배열도 미리 저장
var tempElements = elements
// 기준이 되는 원소는 배열에서 삭제
tempElements.remove(at:i)
// 기준 원소를 제외한 배열의 조합을 구하고
let subCombos = combinations(tempElements, k-1)
// 위 결과를 기반으로 기준 원소와 각각 합친 값들을 얻는다.
let subarray = subCombos.compactMap { temp + $0 }
// subcombo와 유니크한 subarray를 구하여 더해준다.
result = result.union(subCombos)
result = result.union(Set(subarray))
}
return result
}
func isPrime(_ n: Int) -> Bool {
// 소수일 경우 true, 아니면 false
var state = true
// 0,1을 제외하고 2부터 해당 값의 배수인지 확인한다.
for i in 2..<n {
// 배수에 해당된다면 소수의 자격 충족 X
if n % i == 0 {
// false처리해주고 바로 반복문을 종료한다.
state = false
break
}
}
return state
}
자세한 과정들은 달린 주석을 보자!
에라토스테네스의 체라는 것을 듣기만 했고 알아본 것은 처음인 것 같다.
그리고 조합을 입맛대로 사용할 수 있게 여러가지로 변형해보는 것도 중요한 것 같다.
끝