Easy - Binary Watch

https://leetcode.com/problems/binary-watch/description/

Binary Watch - LeetCode

문제 설명

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

• For example, the below binary watch reads "4:51".

Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

The hour must not contain a leading zero.

• For example, "01:00" is not valid. It should be "1:00".

The minute must be consist of two digits and may contain a leading zero.

• For example, "10:2" is not valid. It should be "10:02".

Constraints:

• 0 <= turnedOn <= 10

예시

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Input: turnedOn = 9
Output: []

풀이

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        if turnedOn > 8:
            return []
        if turnedOn == 0:
            return ['0:00']

        ret = []
        
        def to_time(arr: list):
            hour = 0
            minute = 0
            
            for idx in arr:
                if idx <= 3:
                    hour += 2 ** (3 - idx)
                else:
                    minute += 2 ** (9 - idx)
            
            if hour > 11 or minute > 59:
                return False

            return f'{hour}:{minute:02d}'

        def search(cur_idx, taken):
            str_time = to_time(taken)
            reached_end = len(taken) == turnedOn
            
            if not str_time:
                return

            if len(taken) == turnedOn:
                ret.append(str_time)
                return

            for i in range(cur_idx, 10):
                taken.append(i)
                search(i + 1, taken)
                taken.pop()
        
        search(0, [])
        return ret

백트랙을 해도 되고, BFS, DFS 뭐든 탐색만 하면 된다.

이진법 수의 배열을 만들고, 배열로 만들어진 수가 조건에 맞지 않으면 early exit한다.

배열의 길이와 turnedOn이 같을 경우 정답이므로 ret에 추가하고, 더 이상 재귀하지 않는다.

이외의 경우, 다음 인덱스를 추가해서 재귀한다.