DFS


Overview


DFS(Depth First Search)

practice

import (
    "math"
    "strconv"
)

type set map[interface{}]struct{}
func (s set) Insert(v interface{}) {
    s[v] = struct{}{}
}
func (s set) length() int {
    return len(s)
}

func solution(numbers string) int {
    primes := set{}
    depth := make([]bool, len(numbers), )
   
    dfs(numbers, "", depth, primes)
    return primes.length()
}

func dfs(numbers string, checkNumber string, depth []bool, primes set) {
    if len(numbers) == len(checkNumber) {
        return
    }

    for i := range numbers {
        if depth[i] {
            continue
        }
        depth[i] = true
        nextCheckNumber := checkNumber + string(numbers[i])
        if isPrimeNumber(nextCheckNumber) {
            primes.Insert(nextCheckNumber)
        }
        dfs(numbers, nextCheckNumber, depth, primes)
        depth[i] = false
    }
}

func isPrimeNumber(stringNumber string) bool {
    if stringNumber[0] == '0' {
        return false
    }
    number, _ := strconv.Atoi(stringNumber)
    if number <= 1 {
        return false
    }
    sqrtNum := int(math.Sqrt(float64(number)))
    for i := 2; i <= sqrtNum; i++ {
        if number % i == 0 {
            return false
        }
    }
    return true
}

reference


https://programmers.co.kr/learn/courses/30/lessons/42839