알고리즘 - 프로그래머스 소수 찾기 [완전 탐색] (Swift)

Algorism

알고리즘 - 프로그래머스 소수 찾기 [완전 탐색] (Swift)

codinglearn 2020. 7. 16. 18:21

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

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

제한사항

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

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

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

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

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

어렵네요. 풀고 생각을해도 테스트 케이스에서 1~2문제는 성능이 완전 떨어지네요. 네.. 더 공부해야할거 같아요.

먼저 이 문제에서 필요한 선행학습은 순열, 탐색, 소수, 재귀 등이 필요 합니다.

네 그래서 푸는데 오래 걸렸어요. ㅜㅜ 정확한 풀이 방법이 아닐 수도 있지만.!?

전체 코드

import Foundation

func permutation(_ input: String) -> Array<Int> {
    let inputArray = Array(input).map { String($0) }
    var resultArray: Set<Int> = []
    
    func heap(_ array: [String], _ depth:Int, _ outNumber: Int) {
        var arr = array
        
        for index in depth..<arr.count{
            arr.swapAt(depth, index)
            resultArray.insert(Int(arr[0...depth].joined())!)
            print("insert depth = (\(depth)), index = \(index), outNumber = \(outNumber), num = \(arr[0...depth].joined())")
            
            if depth < inputArray.count {
                heap(arr, depth + 1, outNumber+1)
            }
        }
    }
    
    heap(inputArray, 0, 1)
    
    return Array(resultArray)
}

func isPrime(_ numbers: Int) -> Bool {
    
    // 1은 소수가 아니지요.
    if numbers <= 1 {
        return false
    }
    
    // 2, 3은 소수 입니다.!?
    if numbers == 2 || numbers == 3 {
        return true
    }

    // 소수 구하는 공식은 -> 2부터 자신의 제곱근까지 나눠서 나머지가 0이 되지 않아야 한다.
    // 약식으로 본인의 값 / 2 까지만 진행 할게요.
    for index in 2...(numbers/2) {
        if numbers % index == 0 {
            return false
        }
    }

    return true
}


func solution(_ numbers:String) -> Int {

    let numbersArray = permutation(numbers)

    let primeArray = numbersArray.filter { isPrime($0) }

    return primeArray.count
}

일단은 제가 문제를 해결한 방법에 대해서 아래에서 설명을 이어갈게요.

문제 요건

1. 입력받은 String형태의 문자열의 조합으로 소수의 갯수를 반환한다.
2. 입력받은 String문자열로 조합 가능한 규칙은 다음과 같다.
   - 입력 17 : 1, 7, 17, 71 -> 반환 소수 3개 [7, 17, 71]
   - 입력 123 : 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 131, 213, 231, 312, 321
3. 001의 경우처럼 앞자리의 0은 생략한다.
   - 입력 011 -> 생성 가능 문자열 : 0, 1, 10, 11, 101, 110,

네... 읽어 보시면 일반적인 순열하고는 다릅니다. (제가 알고 있기론)

보통의 순열 조건은 아래와 같이 자릿수는 동일하게 생성을 하조.

input = [123]

output = [123], [132], [213], [231], [312], [321]

네 위의 문제요건을 명확히 이해하셨다면 이제 해결하시는 방법은 그렇게 어렵지 않아요.

먼저 입력받은 문자열로 생성 가능한 숫자 조합을 만들고 그 숫자 조합들 중에서 소수의 갯수를 파악해서 반환하면 됩니다.

func solution(_ numbers:String) -> Int {

    let numbersArray = permutation(numbers)

    let primeArray = numbersArray.filter { isPrime($0) }

    return primeArray.count
}

문자열로 생성 가능한 숫자 조합은 아래와 같이 진행을 하였어요.

- 문자열 Array<String> Type 분해

- 문자열 조합 생성 (swapAT 함수 사용) -> 자릿수를 바꾸는 함수입니다.

- 배열에 추가해서 반환

func permutation(_ input: String) -> Array<Int> {
    let inputArray = Array(input).map { String($0) }
    var resultArray: Set<Int> = []
    
    func heap(_ array: [String], _ depth:Int, _ outNumber: Int) {
        var arr = array
        
        for index in depth..<arr.count{
            arr.swapAt(depth, index)
            resultArray.insert(Int(arr[0...depth].joined())!)
            print("insert depth = (\(depth)), index = \(index), outNumber = \(outNumber), num = \(arr[0...depth].joined())")
            
            if depth < inputArray.count {
                heap(arr, depth + 1, outNumber+1)
            }
        }
    }
    
    heap(inputArray, 0, 1)
    
    return Array(resultArray)
}

천천이 하나식 알아볼게요.

먼저 입력받은 문자를 Array<String> 타입으로 변환한 배열을 선언해줍니다.

그리고 반환해줄 배열을 생성해주는데 Set타입으로 생성한 이유는 Set타입은 중복되는 값이 들어가지 않기 때문입니다.

#재귀함수 사용시 프로그래머스에서는 중복되는 값이 발생하는 것 같아요.....

    let inputArray = Array(input).map { String($0) }
    var resultArray: Set<Int> = []

그리고 문자열을 재조합할 heap이라는 펑션을 생성하고 실행해주면서 재귀함수를 진행할거에요.

그이전에 아래 그림으로 어떻게 문자열을 재조합하는지 그림으로 알아볼게요.

먼저 문자열이 변환되는 과정과 우리가 최종적으로 얻어야하는 내용을 위의 그림으로 표현해봤어요.

# 파랑색으로 표기된 부분이 값이 바뀌는 자리이며 동시에 우리가 추출해야할 값입니다.

입력 받은 문자열이 123 이렇게 있을경우 아래처럼 아래쪽으로 순환을 돌며 문자의 자릿수를 변경하며,

depth라는 구분값으로 문자열을 꺼내올겁니다.

0depth에서는 1,2,3의 값을 추출

1depth에서는 12, 13, 21, 23, 31, 32 값을 추출

2depth에서는 123, 132, 213, 231, 312, 321 값을 추출

간단하조?!

위에 처럼 변환하기 위해서는 Swift의 swapAt함수를 사용하여 자리를 변환할 수 있습니다.

아래의 코드에서처럼 변경을 원하는 자리 2개의 인덱스를 인자값으로 호출하면 배열의 자리가 변환됩니다.

# func swapAt(_ i: Int, _ j: Int)

var arrA = [1, 2, 3]

arr.swapAt(0,1)
// [1, 2, 3] -> [2, 1, 3]

arr.swapAt(0,1)
// [2, 1, 3] -> [1, 2, 3]

arr.swapAt(0,2)
// [1, 2, 3] -> [3, 2, 1]

위 함수를 사용하여 변환되는 과정을 아래 그림에서 설명할게요.

위에 보시면 각 뎁스에서 다른 자리의 값을 변환하는 것을 볼수 있을거에요.

먼저 0depth에서는 첫번째 자리만 교체합니다.

그리고 1depth에서는 위에서 변경된 배열을 기준으로 다시 두번째 자리만 변환하조

그리고 마지막 3depth에서도 위와 동일하게 세번째 자리만 변경합니다.

# 여기에서 중요한 부분은 이전 depth의 값을 그대로 사용한다는 부분입니다.

결국 swapAt함수로 변경된 값을 그 아래 Depth에서 그대로 사용한다는 부분이에요.

마지막으로 값이 추출되는 결과인데요.

변경된 값에 대해서 배열의 0...depth만큼 값을 추출할 겁니다.

그러면 0depth에서는 1개의 자릿수만 추출하게 되고, 1depth에서는 2개의 자리... 그러면 원하는 값을 모두 꺼낼 수 있겠조?

네 설명이 길었어요... 하하.. 이제 코드를 보시면 더욱 잘 이해가 가실 거에요.

먼저 재귀함수를 호출 부분에는 입력받은 문자 배열, 뎁스, 그리고 출력할 문자 갯수 이렇게 3개입니다.

# 0depth에서 1개의 문자열만 추출할 것이기 때문에 아래 처럼 첫인자는 depth는 0, outNumber는 1 이렇게 호출 하였습니다.

heap(array: inputArray, depth: 0, outNumber: 1)

func heap(_ array: [String], _ depth:Int, _ outNumber: Int) {
    var arr = array
    
    for index in depth..<arr.count{
        arr.swapAt(depth, index)
        resultArray.insert(Int(arr[0...depth].joined())!)
        if depth < inputArray.count {
            heap(arr, depth + 1, outNumber+1)
        }
    }
}

먼저 입력받은 배열을 변경 가능한 arr의 변수에 복사해줄게요.

그리고 for문을 도는데 첫 시작 값이 depth이고 종료하는 값을 입력 받은 글자수 까지 입니다.

위에서 그림으로 설명했듯이 해당 depth에서는 그 자리수의 값만을 변경하기 때문이조.

그리고 swapAt로 해당 뎁스의 값과 다음 인덱스 값을 변경하게 되조.

그리고 반환받을 배열에 Int타입으로 형변환해줘서 담아줍니다.'

그리고 재귀 할수를 호출하는데 depth와, 추출할 글자수를 1식 증가시켜서 다음 뎁스를 진행할 겁니다.

이때 재귀함수를 호출 하는 시점은 depth의 값이 문자열 갯수를 넘지 않을때 까지만 진행해주면 됩니다.

이렇게 진행하게 되면 위의 그림에서 설명했는이 아래의 로그 값처럼 값이 추출 되게 됩니다.

# 2 자리

insert depth = (0), index = 0, outNumber = 1, num = 1
insert depth = (1), index = 1, outNumber = 2, num = 12
insert depth = (0), index = 1, outNumber = 1, num = 2
insert depth = (1), index = 1, outNumber = 2, num = 21
numbersArray count = 4, NumbersArray = [1, 21, 2, 12]
primeArray count = 1, primeArray = [2]
result is Prime Count = 1

# 3 자리

insert depth = (0), index = 0, outNumber = 1, num = 1
insert depth = (1), index = 1, outNumber = 2, num = 12
insert depth = (2), index = 2, outNumber = 3, num = 123
insert depth = (1), index = 2, outNumber = 2, num = 13
insert depth = (2), index = 2, outNumber = 3, num = 132
insert depth = (0), index = 1, outNumber = 1, num = 2
insert depth = (1), index = 1, outNumber = 2, num = 21
insert depth = (2), index = 2, outNumber = 3, num = 213
insert depth = (1), index = 2, outNumber = 2, num = 23
insert depth = (2), index = 2, outNumber = 3, num = 231
insert depth = (0), index = 2, outNumber = 1, num = 3
insert depth = (1), index = 1, outNumber = 2, num = 31
insert depth = (2), index = 2, outNumber = 3, num = 312
insert depth = (1), index = 2, outNumber = 2, num = 32
insert depth = (2), index = 2, outNumber = 3, num = 321
numbersArray count = 15, NumbersArray = [21, 31, 3, 321, 13, 123, 231, 312, 23, 32, 1, 12, 2, 132, 213]
primeArray count = 5, primeArray = [31, 3, 13, 23, 2]
result is Prime Count = 5

# 4 자리

insert depth = (0), index = 0, outNumber = 1, num = 1
insert depth = (1), index = 1, outNumber = 2, num = 12
insert depth = (2), index = 2, outNumber = 3, num = 123
insert depth = (3), index = 3, outNumber = 4, num = 1234
insert depth = (2), index = 3, outNumber = 3, num = 124
insert depth = (3), index = 3, outNumber = 4, num = 1243
insert depth = (1), index = 2, outNumber = 2, num = 13
insert depth = (2), index = 2, outNumber = 3, num = 132
insert depth = (3), index = 3, outNumber = 4, num = 1324
insert depth = (2), index = 3, outNumber = 3, num = 134
insert depth = (3), index = 3, outNumber = 4, num = 1342
insert depth = (1), index = 3, outNumber = 2, num = 14
insert depth = (2), index = 2, outNumber = 3, num = 142
insert depth = (3), index = 3, outNumber = 4, num = 1423
insert depth = (2), index = 3, outNumber = 3, num = 143
insert depth = (3), index = 3, outNumber = 4, num = 1432
insert depth = (0), index = 1, outNumber = 1, num = 2
insert depth = (1), index = 1, outNumber = 2, num = 21
insert depth = (2), index = 2, outNumber = 3, num = 213
insert depth = (3), index = 3, outNumber = 4, num = 2134
insert depth = (2), index = 3, outNumber = 3, num = 214
insert depth = (3), index = 3, outNumber = 4, num = 2143
insert depth = (1), index = 2, outNumber = 2, num = 23
insert depth = (2), index = 2, outNumber = 3, num = 231
insert depth = (3), index = 3, outNumber = 4, num = 2314
insert depth = (2), index = 3, outNumber = 3, num = 234
insert depth = (3), index = 3, outNumber = 4, num = 2341
insert depth = (1), index = 3, outNumber = 2, num = 24
insert depth = (2), index = 2, outNumber = 3, num = 241
insert depth = (3), index = 3, outNumber = 4, num = 2413
insert depth = (2), index = 3, outNumber = 3, num = 243
insert depth = (3), index = 3, outNumber = 4, num = 2431
insert depth = (0), index = 2, outNumber = 1, num = 3
insert depth = (1), index = 1, outNumber = 2, num = 31
insert depth = (2), index = 2, outNumber = 3, num = 312
insert depth = (3), index = 3, outNumber = 4, num = 3124
insert depth = (2), index = 3, outNumber = 3, num = 314
insert depth = (3), index = 3, outNumber = 4, num = 3142
insert depth = (1), index = 2, outNumber = 2, num = 32
insert depth = (2), index = 2, outNumber = 3, num = 321
insert depth = (3), index = 3, outNumber = 4, num = 3214
insert depth = (2), index = 3, outNumber = 3, num = 324
insert depth = (3), index = 3, outNumber = 4, num = 3241
insert depth = (1), index = 3, outNumber = 2, num = 34
insert depth = (2), index = 2, outNumber = 3, num = 341
insert depth = (3), index = 3, outNumber = 4, num = 3412
insert depth = (2), index = 3, outNumber = 3, num = 342
insert depth = (3), index = 3, outNumber = 4, num = 3421
insert depth = (0), index = 3, outNumber = 1, num = 4
insert depth = (1), index = 1, outNumber = 2, num = 41
insert depth = (2), index = 2, outNumber = 3, num = 412
insert depth = (3), index = 3, outNumber = 4, num = 4123
insert depth = (2), index = 3, outNumber = 3, num = 413
insert depth = (3), index = 3, outNumber = 4, num = 4132
insert depth = (1), index = 2, outNumber = 2, num = 42
insert depth = (2), index = 2, outNumber = 3, num = 421
insert depth = (3), index = 3, outNumber = 4, num = 4213
insert depth = (2), index = 3, outNumber = 3, num = 423
insert depth = (3), index = 3, outNumber = 4, num = 4231
insert depth = (1), index = 3, outNumber = 2, num = 43
insert depth = (2), index = 2, outNumber = 3, num = 431
insert depth = (3), index = 3, outNumber = 4, num = 4312
insert depth = (2), index = 3, outNumber = 3, num = 432
insert depth = (3), index = 3, outNumber = 4, num = 4321

numbersArray count = 64, NumbersArray = [123, 143, 2341, 423, 2413, 1234, 4231, 24, 241, 214, 1342, 2431, 23, 1243, 124, 413, 1, 43, 4321, 342, 13, 314, 324, 2, 243, 321, 4213, 4, 3142, 1423, 1324, 31, 3214, 2143, 21, 42, 132, 32, 3412, 312, 34, 3241, 134, 4312, 3, 14, 234, 1432, 2314, 41, 431, 12, 3124, 432, 412, 341, 3421, 231, 4123, 2134, 142, 213, 4132, 421]
primeArray count = 14, primeArray = [2341, 4231, 241, 23, 43, 13, 2, 1423, 31, 2143, 3, 41, 431, 421]
result is Prime Count = 14

네 이제 반환받은 함수를 소수 판별을 진행해줄건데요.

이내용은 이전에도 많이 다뤘기 때문에?! 간단하게 코드로만 설명하고 넘어갈게요.

func isPrime(_ numbers: Int) -> Bool {
	
    // 1은 소수가 아니지요.
    if numbers <= 1 {
        return false
    }
	
    // 2, 3은 소수 입니다.!?
    if numbers == 2 || numbers == 3 {
        return true
    }

	// 소수 구하는 공식은 -> 2부터 자신의 제곱근까지 나눠서 나머지가 0이 되지 않아야 한다.
    // 약식으로 본인의 값 / 2 까지만 진행 할게요.
    for index in 2...(numbers/2) {
        if numbers % index == 0 {
            return false
        }
    }

    return true
}

길이 너무 길었조... 읽어주셔서 고맙습니다.

저두 아직 공부하는 중이라 내용에 대한 전달이 부족하고 정확하지 않을 수 있어요.. 참고해주세요.

# [번외-참고용] 중복값까지 허용한 모든 경우의 수 구하기

func permutation(_ items: String) -> Array<Int> {
    var scratch = Array(items).map { String($0) }
    var result: Set<Int> = []
    
    func heap(_ outputp: [String], _ depth:Int, _ number: Int, _ r: Int) {
        var output = outputp
        if depth == r {
            print("heap return depth = \(depth), r = \(r)", output)
            return
        }
        
        for index in 0..<number{
            output[depth] = scratch[index]
            print("insert output = \(output[depth])")
            heap(output, depth+1, number, r)
        }
    }
    
    heap([String](repeating: "", count: scratch.count) , 0, scratch.count, 3)
    
    
    return Array(result)
}

heap return depth = 3, r = 3 ["0", "0", "0"]
heap return depth = 3, r = 3 ["0", "0", "1"]
heap return depth = 3, r = 3 ["0", "0", "2"]
heap return depth = 3, r = 3 ["0", "1", "0"]
heap return depth = 3, r = 3 ["0", "1", "1"]
heap return depth = 3, r = 3 ["0", "1", "2"]
heap return depth = 3, r = 3 ["0", "2", "0"]
heap return depth = 3, r = 3 ["0", "2", "1"]
heap return depth = 3, r = 3 ["0", "2", "2"]
heap return depth = 3, r = 3 ["1", "0", "0"]
heap return depth = 3, r = 3 ["1", "0", "1"]
heap return depth = 3, r = 3 ["1", "0", "2"]
heap return depth = 3, r = 3 ["1", "1", "0"]
heap return depth = 3, r = 3 ["1", "1", "1"]
heap return depth = 3, r = 3 ["1", "1", "2"]
heap return depth = 3, r = 3 ["1", "2", "0"]
heap return depth = 3, r = 3 ["1", "2", "1"]
heap return depth = 3, r = 3 ["1", "2", "2"]
heap return depth = 3, r = 3 ["2", "0", "0"]
heap return depth = 3, r = 3 ["2", "0", "1"]
heap return depth = 3, r = 3 ["2", "0", "2"]
heap return depth = 3, r = 3 ["2", "1", "0"]
heap return depth = 3, r = 3 ["2", "1", "1"]
heap return depth = 3, r = 3 ["2", "1", "2"]
heap return depth = 3, r = 3 ["2", "2", "0"]
heap return depth = 3, r = 3 ["2", "2", "1"]
heap return depth = 3, r = 3 ["2", "2", "2"]