[Swift] 소수 찾기 코딩테스트 프로그래머스

재귀함수 DFS 에 익숙하지 않아서 문제를 해결하는는데 오래 걸렸다

해당 문제는 DFS를 사용해 만들수 있는 모든 경우의 수를 만들고

해당 수가 소수인지 체크후 배열에 넣으면 되는 문제이다.

중요한것은 DFS를 사용해 경우의 수를 만드는 일이었기 떄문에

소수를 분별 하는것은 짧게 설명한다.

 

소수

소수는 1말고 약수가 없는수다. 11 이나 13이런건 1말고 나누어 떨어지는 수가없다.

이런거는 해당 수의 제곱근이 그보다 적은 숫자로 나누어 떨어지는지 아닌지 체크하면 된다.

for i in 2...숫자의 제곱근+1{
      if(num % i == 0){
          return false
      }
  }

나누어 떨어지면 소수가 아니므로 패스하면된다.

여기서 1은 소수가 아니고 2는 체크할것없이 소수가 맞으니 패스한다.

func isPrime(num:Int) -> Bool{
        guard num > 1 else {
            return false
        }
        guard num != 2 else {
            return true
        }

        for i in 2...Int(sqrt(Double(num)))+1{
            if(num % i == 0){
                return false
            }
        }
        return true
    }

 

 

 

 

이제 모든 경우의 수를 찾는방법이다.

한번에 모든 조건을 넣으니 복잡하고 꼬여서 우선 구현을 차근차근 하기로했다.

1. 모든 수 만들기 (가능한 자릿수만큼만)
2. 사용한 수 못쓰게 하기
3. 중복 제거하기 & 소수 구별하기

 

모든수 만들기

 

모든 수를 만든다는것은 [1,2,3] 이있으면

111,112 이렇게 숫자를 중복해서도 만들수도 있다는것이다.

for i in 0..<arr.count{
    dfs(depth:0,length:i+1,number: "") //1,2,3
}

dfs를 시작하는 부분이다.

 

여기서는 반복문을 통해 몇자리수를 만들지정해진다.

첫번쨰 반복문은 한자리수

두번째 반복문은 두자리수를 의미한다.

length는 그것을 의미하고

 

number는 완성해나갈 값이다.  “” 에서 숫자를 집어 넣을것이다.

depth는 지금 number의 자릿수를 의미한다.

 

여기서 한싸이클이 돌면 해당 자리수의 dfs가 끝났다는 의미이다.

예로 한자리수 싸이클이 다 돌았다면 [1,2,3] 이 리턴 되었다는 것이다.

 

 

func dfs(depth:Int,length:Int,number:String){
        if(length == depth){
          let value = Int(number)!
             result.append(value)
        }else{
            
            for i in 0..<arr.count{ 
                dfs(depth: depth+1,length: length,number: number+arr[i])
            }
        }
    }

dfs 부분이다.

length는 원하는 자릿수를 의미한다 했다.

depth는 지금 Number의 자릿수이다. 만약 원하는 자릿수가 지금 number의 자릿수와 같다면

해당 number 를 리턴해주면 되는것이다.

 

만약 그게 아니라면 자리수가 부족하다는 의미이므로 뒤에 숫자를 더 추가 해 줘야한다.

세자리 수의 값을 원하는데 지금 number 는 “12” 인 상황이라고 보면된다.

다음 재귀를 돌릴때 number의 값을 추가시켜주고

depth를 높여줌으로써 다음 함수에는 세자리수가 완성되어 리턴될것이다.

 

이렇게 하면 모든 수가 만들어진다.

 

 

숫자 중복사용 막기

 

이제 사용한 숫자를 또 못쓰게 하는 방법이다.

이때는 사용했는지 안했는지 체크할 배열이 필요하다.

var checkedList = Array(repeating: false, count: arr.count)

길이는 숫자배열의 길이와 같고 값을 false 로 두었다. 아직 사용 안했다는 뜻이다.

for i in 0..<arr.count{
        dfs(depth:0,length:i+1,number: "") //1,2,3
        checkedList = Array(repeating: false, count: arr.count)
    }

dfs 처음 실행하는 부분에서 한 싸이클이 끝나면 checkList를 초기화 해줘야한다.

첫싸이클에서 1,2,3 숫자들을 사용한 상태로 끝나기 떄문에 초기화 해줬다.

func dfs(depth:Int,length:Int,number:String){
        if(length == depth){
            let value = Int(number)
                result.append(value)

        }else{
            
            for i in 0..<arr.count{ //하나씩 추가
                
                if(checkedList[i] == false){
                    checkedList[i] = true
                    
                    dfs(depth: depth+1,length: length,number: number+arr[i])
                    checkedList[i] = false
                }
            }
        }
    }

else문만 수정이되었다.

숫자를 추가할때 checkList[i] = true로 수정했다.

이말은 1,2,3 중에 1을 사용했다면

1은 사용 했음을 표시해둔것이다.

이렇게 함으로써 다음 dfs에서 1은 사용할수없다.

 

중요한건 dfs호출 밑에 다시 checkList[i] = false로 수정한 부분이다.

해당 코드는 위에 실행한 dfs가 모두 끝난뒤에 실행된다.

예로 12로 시작되는 숫자가 만들어진 이후에 (ex> 이전에 123을 만들고 끝남)

13으로 시작되는 숫자를 만들어야하는데 위에서 2를 사용했기 떄문에 132를 만들지 못하는

경우를 피한것이다.

 

이렇게 하면 숫자 중복 사용을 피한 모든 숫자가 만들어진다.

 

 

마지막으로 결과값 중복 체크와 아까 만들어놓은 소수 체크를 해주면 완성된다.

 

 

전체 코드

func solution(_ numbers:String) -> Int {
   
    let arr = numbers.map{String($0)}
    
    var result = [Int]()
    
    func isPrime(num:Int) -> Bool{
        guard num > 1 else {
            return false
        }
        guard num != 2 else {
            return true
        }

        for i in 2...Int(sqrt(Double(num)))+1{
            if(num % i == 0){
                return false
            }
        }
        return true
    }
    
    
    var checkedList = Array(repeating: false, count: arr.count)
    func dfs(depth:Int,length:Int,number:String){
        if(length == depth){
            let value = Int(number)!
            if(!(result.contains(value)) && isPrime(num: value)){
                result.append(value)

            }

        }else{
            
            for i in 0..<arr.count{ //하나씩 추가
                
                if(checkedList[i] == false){
                    checkedList[i] = true
                    
                    dfs(depth: depth+1,length: length,number: number+arr[i])
                    checkedList[i] = false
                }
            }
        }
    }
  
    

    for i in 0..<arr.count{
        dfs(depth:0,length:i+1,number: "") //1,2,3
        checkedList = Array(repeating: false, count: arr.count)
    }
    
   
    return result.count
}