[Golang으로 도전하는 Leetcode] Largest Time for Given Digits

오늘 풀 문제는 Largest Time for Given Digits라는 문제이며

링크는 https://leetcode.com/problems/largest-time-for-given-digits/입니다

이번에 접근은 map을 써서 순차적으로 4자리 숫자를 구해보는식으로 해보았는데

반례에 걸려서 조합으로 다 구한 뒤에 조건을 걸어서 찾는 형식으로 바꿔서 풀어보았습니다

첫번째로는 map을 사용해서 0부터 9까지 갯수를 구한 뒤에 맨 앞부터 큰 시간순대로 시간을 만들었는데

반례에 걸려서 알고리즘을 바꾸었습니다

첫번째 알고리즘 코드입니다

func largestTimeFromDigits(A []int) string {
    m := make(map[int]int)
    i := 0
    result := ""
    flag := false
    for i <10 {
        m[i] = 0
        i += 1
    }
    for _, item := range A {
        m[item] += 1
    }
    //first
    i = 2
    for i > -1 {
        if m[i] != 0 {
            m[i] -= 1
            result += strconv.Itoa(i)
            flag = true
            break
        }
        i -= 1
    }
    if flag == false{
        return ""
    }
    //second
    flag = false
    if result == "2"{
        i = 3
        for i > -1 {
            if m[i] != 0 {
                m[i] -= 1
                result += strconv.Itoa(i)
                flag = true
                break
            }
            i -= 1
        }
        if flag == false{
            return ""
        }
    }else{
        i = 9
        for i > -1 {
            if m[i] != 0 {
                m[i] -= 1
                result += strconv.Itoa(i)
                flag = true
                break
            }
            i -= 1
        }
        if flag == false{
            return ""
        }
    }
    result += ":"
    //third
    flag = false
    i = 5
    for i > -1 {
        if m[i] != 0 {
            m[i] -= 1
            result += strconv.Itoa(i)
            flag = true
            break
        }
        i -= 1
    }
    if flag == false{
        return ""
    }
    //fourth
    flag = false
    i = 9
    for i > -1 {
        if m[i] != 0 {
            m[i] -= 1
            result += strconv.Itoa(i)
            flag = true
            break
        }
        i -= 1
    }
    if flag == false{
        return ""
    }
    return result
}

 이 코드는 반례가 아래와 같습니다

Input:
[2,0,6,6]
Output:
""
Expected:
"06:26"

제 코드는 2가 있으면 맨앞에 고정되기 때문에 이런식으로 반례가 나오게 되었습니다

따라서 두 번째 방법인 조합을 사용해서 모든 조합을 다 구한뒤에 조건에 맞게 결과가 나오도록 알고리즘을 구현하였습니다

func permutations(arr []int)[][]int{
    var helper func([]int, int)
    res := [][]int{}

    helper = func(arr []int, n int){
        if n == 1{
            tmp := make([]int, len(arr))
            copy(tmp, arr)
            res = append(res, tmp)
        } else {
            for i := 0; i < n; i++{
                helper(arr, n - 1)
                if n % 2 == 1{
                    tmp := arr[i]
                    arr[i] = arr[n - 1]
                    arr[n - 1] = tmp
                } else {
                    tmp := arr[0]
                    arr[0] = arr[n - 1]
                    arr[n - 1] = tmp
                }
            }
        }
    }
    helper(arr, len(arr))
    return res
}

func makeStr(A []int) string {
    return strconv.Itoa(A[0]) + strconv.Itoa(A[1]) + strconv.Itoa(A[2]) +strconv.Itoa(A[3])
}

func largestTimeFromDigits(A []int) string {
    per := permutations(A)
    flag := false
    result := "0000"
    for _, item := range per {
        times := makeStr(item)
        if times < "2400" && times[2:] <"60"{
            if result < times{
                result = times
            }
            flag = true
        }
    }
    if flag == false{
        return ""
    }
    return result[:2] + ":" + result[2:]
}

모든 조합을 다 구하고 2400보다 낮은 수에서 뒤의 2자리가 분 표시가 되는 조건들 중 가장 큰 값을 구하였습니다

감사합니다