🔍401. Binary Watch - [백트래킹, 비트마스킹]

https://leetcode.com/problems/binary-watch/description/?envType=problem-list-v2&envId=backtracking

 

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 consist of two digits and may contain a leading zero.

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

 

Example 1:

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

Example 2:

Input: turnedOn = 9
Output: []

 

Constraints:

• 0 <= turnedOn <= 10

---

 

---

 

예시 해석

[설명]

※ <그림>의 시계는 이진법으로 표시되어 있음

   - 시에 해당하는 8, 4, 2, 1을 모두 더하면 12를 넘기므로, 모든 숫자에 불이 켜지지는 않을 것임

   - 분에 해당하는 32, 16, 8, 4, 2, 1을 모두 더하면 60을 넘지만, 문제에서 분의 범위를 0-59로 지정했으므로 모든 숫자에         불이 켜지지는 않을 것임

 

※ 따라서 <그림>의 시계가 "4:51"인 이유는

    - 시 : 4

    - 분 : 32 + 16 + 2 + 1 = 51 

 

 

[예시 1]

※ LED 수가 1개 = 1) H만 불이 들어오거나(=정각) 

                              2) H는 0시로 고정하고 0:32, 16, 8, 4, 2, 1 

※ 1)의 경우의 수 : ["1:00","2:00","4:00","8:00"]

    2)의 경우의 수 : ["0:01","0:02","0:04","0:08","0:16","0:32"]

 

 

[예시 2]

1. LED 수가 9개 = H에서 최대한 켤 수 있는 LED의 수는 3개(4+2+1=7시. 8+4+2+1은 11을 초과해서 안됨)
2. 결국 M에서 6개를 켜야 하는데, 이떄 6개의 숫자를 모두 더하면 60을 넘겨버림
3. 따라서 가능한 경우의 수는 없다. []

 

---

※ 참고로 Python 말고 Python3에서 구현할 것

class Solution:
	def readBinaryWatch(self, turnedOn: int) -> List[str]:
    	answer = []
        for h in range(12):
        	for m in range(60):
            	temp = bin(h) + bin(m)
                if temp.count("1") == turnedOn :
                	time = '%d:%02d'% (h,m)
                    output.append(time)
        return answer

 

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        output = []
        # Loop through all possible combinations of hours and minutes and count the number of set bits
        for h in range(12):
            for m in range(60):
                if bin(h).count('1') + bin(m).count('1') == turnedOn:  # Check if the number of set bits in hours and minutes equals the target number
                    output.append(f"{h}:{m:02d}")  # Add the valid combination of hours and minutes to the output list
        return output

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        times = []
        for h in range(12):
            for m in range(60):
                if (bin(h) + bin(m)).count('1') == turnedOn:
                    times.append(f'{h}:{m:02d}')
        return times

---

참고자료

- https://youtu.be/0BanwDe6cMY?si=g_SnRYdN3eperoiW

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