Swift) LeetCode(Easy) - Binary Watch (BackTracking)

leetcode.com/problems/binary-watch/

Binary Watch - LeetCode

안녕하세요 후르륵짭짭 입니다.

이번에는 BackTracking 문제를 풀어봤습니다.

처음에는 어떻게 풀지,,, 생각했는데,, 기본적인 DFS를 이용한 백트레킹을 이용하면 금방 풀 수 있습니다.

백 트레킹이란 완전 탐색 방법의 일종이지만 조건을 주어서 그 조건에 해당하는 경우만 대상으로 하는 것을 의미합니다.

 

** 제가 푼 방법 **

일단 제가 푼 방법은 복잡하고 좋지 못하지만

DFS를 이용하여 조합을 사용했습니다. 그래서 좀더 이론에 충실한 코드라 생각되지만 ㅎㅎㅎ

참신하지 않고 일반적이다라는 생각 입니다.

class Solution {
    
    let hourList : [Int] = [1,2,4,8]
    var hourcheck : [Int] = Array(repeating: 0, count: 4)
    let minutesList : [Int] = [1,2,4,8,16,32]
    var minutescheck : [Int] = Array(repeating: 0, count: 6)
    
    var answer : [String] = []
    
    func readBinaryWatch(_ num: Int) -> [String] {
        
        hourCombination(0, num, 0, 0)
        
        return answer
    }
    
    func hourCombination(_ cnt : Int, _ last : Int,_ currentIndex : Int , _ totalHours : Int){
        
        if cnt == last {
            minuteCombination(0, 0 , String(totalHours), 0, 0)
        }
        else{
            
            minuteCombination(0, last - cnt , String(totalHours), 0, 0)
            if currentIndex > 3 {return}
            for index in currentIndex...3{
                
                let nextHour = totalHours + hourList[index]
                
                if nextHour <= 11 && hourcheck[index] == 0 {
                    hourcheck[index] = 1
                    hourCombination(cnt + 1, last, index + 1, nextHour)
                    hourcheck[index] = 0
                }
                
            }
            
        }
        
        
    }
    
    func minuteCombination(_ cnt : Int , _ last : Int, _ hour : String,_ currentIndex : Int , _ totalMinutes : Int){
        
        if cnt == last {
            
          let stringMin = String(totalMinutes)
            
            if stringMin.count < 2 {
                let temp = "\(hour):0\(stringMin)"
                answer.append(temp)
            }
            else{
                let temp = "\(hour):\(stringMin)"
                answer.append(temp)
            }
            
        }
        else{
            
            if currentIndex > 5 {return}
            
            for index in currentIndex...5{
                
               let nextMinutes = totalMinutes + minutesList[index]
                
                if nextMinutes <= 59 && minutescheck[index] == 0 {
                    
                    minutescheck[index] = 1
                    minuteCombination(cnt + 1, last, hour, index + 1 ,nextMinutes)
                    minutescheck[index] = 0
                    
                }
                
            }
            
        }
        
    }
    
    
}

 

** 놀라웠던 코드 **

반면 이 코드를 보고 

"와 이렇게도 풀 수 가 있구나~!"

라고 생각 했습니다.

func readBinaryWatch(_ num: Int) -> [String] {
    var res = [String]()

    func findLEDs(_ h: Int, _ m: Int) -> Int {
        let hc = Array(String(h, radix: 2)).filter { $0 == "1" }.count
        let mc = Array(String(m, radix: 2)).filter { $0 == "1" }.count
        return hc + mc
    }

    for h in 0...11 {
        for m in 0...59 {
            if findLEDs(h, m) == num {
                res.append(String(format: "%d:%02d", h, m))
            }
        }
    }

    return res
}

일단 모든 경우에 대해서 탐색하는 완전 탐색 방법 입니다.

방법은 시간을 나타내는 h 와 분을 나타내는 m 을

반복문을 돌려서 findLEDs 함수에서 2진수로 변경하고 그 숫자를 문자열로 그리고 그것을 String으로 변경한 뒤에

1인 부분의 갯수를 시간과 분을 합해서 반환합니다.

그리고 이 숫자가 입력 값 num 과 같다면 String(format:)으로 출력합니다.

(참고로 %02d 는 자리 수를 2자리로 하는데 빈 곳이 있다면 그 부분을 0으로 채우겠다 라는 것 입니다.

따라서 한자리 수는 0숫자 이렇게 나오고 2자리 수면 숫자 통채로 나오게 되는 겁니다

참고 사이트 : is03.tistory.com/6 )