Leet Code - 401. Binary Watch(C++)

예제: Binary Watch

문제
A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads "3:25".

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

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

NOTE:

* The order of output does not matter.
* 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".

풀이

binary 시계의 led가 켜진 수가 주어졌을 때, 시계가 표시할 수 있는 수의 조합을 출력하는 문제이다.

조합으로만 풀면 되기에 간단한 문제 같지만, 필자가 최근 멘탈이 위협을 받아 헤롱헤롱 하는 탓으로, 조합 알고리즘을 풀어내는 방법을 잊어버려 필자에게는 어려운 문제였다😥.
그래도 next_permutation으로는 풀기 싫어서 나름 풀어보았는데, 코드가 상당히 더러워진 느낌이 있다.

어쨌든 주어진 수 대로 조합을 구해서 시:분 모양으로 만들어주면 되는데, 시는 4개, 분은 6개이므로 주어진 수에서 시의 개수부터 차감해 주어야 입력이 5개 이상의 수가 들어왔을 때 에러가 나지 않는다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	int hour[4] = { 1, 2, 4, 8 };
	int min[6] = { 1, 2, 4, 8, 16, 32 };

	vector<string> readBinaryWatch(int num) {
		vector<string> result;

		vector<string> str1;
		vector<string> str2;

		vector<int> v1;
		vector<int> v2;

		for (int n1 = 0; n1 <= num; n1++) {
			int n2 = num - n1;
			solve(str1, v1, n1);
			solve2(str2, v2, n2);

			for (auto s1 : str1) {
				for (auto s2 : str2) {
					result.push_back(s1 + ":" + s2);
				}
			}

			str1.clear();
			str2.clear();
		}

		return result;
	}

	void solve(vector<string>& str1, vector<int>& v1, int cnt) {
		if (cnt == 0) {
			int res = 0;
			for (auto v : v1) {
				res += hour[v];
			}
			if (res < 12)
				str1.push_back(to_string(res));
		}

		int idx = v1.empty() ? 0 : v1.back() + 1;

		for (int i = idx; i < 4; i++) {
			v1.push_back(i);
			solve(str1, v1, cnt - 1);
			v1.pop_back();
		}
	}

	void solve2(vector<string>& str2, vector<int>& v2, int cnt) {
		if (cnt == 0) {
			int res = 0;
			for (auto v : v2) {
				res += min[v];
			}
			if (res < 60) {
				string sres = to_string(res);
				if (sres.size() == 1)
					sres = "0" + sres;
				str2.push_back(sres);
			}
		}

		int idx = v2.empty() ? 0 : v2.back() + 1;

		for (int i = idx; i < 6; i++) {
			v2.push_back(i);
			solve2(str2, v2, cnt - 1);
			v2.pop_back();
		}
	}
};

풀이 후기

오랜만에 쓰는 포스트이다. Leet Code는 꾸준히 풀었지만..
조금씩 꾸준히 예전의 페이스를 찾으려 노력중이다. 할 수 있겠지!
그나저나 풀이 후기라는 소제목을 달고있지만 풀이 후기라기 보다는 거의 일기에 가까운 느낌이 든다. 소제목을 바꿔야하나..