Leet Code - 38. Count and Say(C++)

예제: Count and Say

문제
The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: 4
Output: "1211"
Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".

풀이

글쎄, 무슨 문제라고 해야할까..
단계가 넘어가면서 해당 문자열을 읽는 문제이다.
1단계가 "1" 이라면, 2단계에서는 1개의 "1"이 있으므로 "11", 3단계에서는 2개의 "1"이 있으므로 "21", 4단계에서는 1개의 "2"와 1개의 "1"이 있으니 "1211"... 이런 식이다.

효율적인 방법이 무엇일까 생각해 보았지만, 주어진 문자열을 단계별로 읽는 방법 외에는 딱히 떠오르지가 않았다.

다이나믹 프로그래밍을 주로 다루다 보니, 재귀함수를 사용하는 방법이 주로 떠오른다.
해당 단계의 문자열을 만든 뒤, 재귀함수로 넘기는 방식으로 구현하였다.

다음은 전체적인 소스코드이다.

소스 코드

class Solution {
public:
	string countAndSay(int n) {
		return solve("1", n);
	}

	string solve(const string& str, int n) {
		if (n == 1) return str;

		char ch = ' ';
		int cnt = 0;
		string res;

		for (int i = 0; i < str.size(); i++) {
			if (ch == ' ' || ch == str[i]) {
				cnt++;
			}
			else {
				res += (to_string(cnt) + str[i - 1]);
				cnt = 1;
			}
			ch = str[i];

			if (i == str.size() - 1) {
				res += (to_string(cnt) + ch);
			}
		}

		return solve(res, n - 1);
	}
};

풀이 후기

다른 사람의 풀이들을 보니, 2중 for문 등으로 필자와 비슷하게 구현한 것이 많았다. 작은 코드 디테일에서 속도차이가 발생하려나.

leetcode 2회차때는 속도와 메모리 다 잡아보도록 노력해야겠다.