[LeetCode # 38 ~ 40] 문제 풀이

# 38. Count and Say

숫자 n 이 주어졌을 때, n-1 로 만들어지는 문자열의 숫자를 Count 하는 문제

CountAndSay(n) = CountAndSay(CountAndSay(n-1))

CountAndSay(1) = "1"

 

ex) CountAndSay(2) = CountAndSay(CountAndSay(1)) = CountAndSay("1")
"1" --> One 1 => "11"

 

이 문제는 Recursive Function 을 만들어서 C&S(1) ~ C&S(n) 까지 만들어 나가는 식으로 해결했다.

C&S(1) 은 위와 같이 단순 "1"이고, C&S(2) 부터는 해당 문자열을 탐색하면서 연속되는 숫자의 개수를 확인하는 방식으로 해당 Index 문제를 해결할 수 있도록 했다.

 

string recursive(int n) {
	if (n == 1)
		return "1";
	string child = recursive(n - 1), ret = "";
	int cur = child[0] - '0', cnt = 1;
	for (int i = 1; i <= child.length(); i++) {
		if (i == child.length()) {
			ret += to_string(cnt);
			ret += to_string(cur);
			break;
		}
		if (child[i] - '0' == cur) {
			cnt++;
		}
		else {
			ret += to_string(cnt);
			ret += to_string(cur);
			cur = child[i] - '0';
			cnt = 1;
		}
	}
	return ret;
}

string countAndSay(int n) {
	return recursive(n);
}

# 39. Combination Sum

정수형 배열이 주어지고 목표로 하는 값이 주어졌을 때, 더해서 주어진 값을 만들 수 있는 경우를 모두 찾는 문제.

* 배열에는 중복된 값이 주어지지 않고 배열에서 하나의 값이 여러 번 사용될 수 있다.

 

이 문제는 DFS 방식으로 문제를 풀었는데 함수 인자로 현재 탐색 중인 배열의 인덱스 값을 주고 그 위치부터 뒤로만 값을 추가할 수 있도록 했다. 최적화한 부분은, 현재까지의 합이 목표값을 넘어간 경우 탐색을 중단하도록 했다.

 

void recursiveSearch(vector<vector<int>>& ans, vector<int>& candidates, int idx, vector<int>& cur_vec, int cur_sum, int target) {
	if (cur_sum > target)
		return;
	if (cur_sum == target) {
		ans.push_back(cur_vec);
		return;
	}

	for (int i = idx; i < candidates.size(); i++) {
		cur_vec.push_back(candidates[i]);
		recursiveSearch(ans, candidates, i, cur_vec, cur_sum + candidates[i], target);
		cur_vec.pop_back();
	}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
	vector<vector<int>> ans;
	vector<int> tmp;
	recursiveSearch(ans, candidates, 0, tmp, 0, target);
	return ans;
}

# 40. Combination Sum II

# 39. 와 유사하지만 차이점은, 배열에 중복값이 존재한다는 점과 Target 값을 만드는 조합이 유일해야 한다는 차이가 있는 문제

 

이 문제도 위와 마찬가지로 DFS 방식으로 문제를 해결했는데 중복된 값이 동일한 위치에 두 번 이상 사용되면 안 되기 때문에 함수 인자로 인덱스를 사용했고, 현재 인덱스 값과 다음 인덱스 값이 같을 경우 그 값을 넘기고 탐색하도록 했다.

 

void recursiveSearch(vector<vector<int>>& ans, vector<int>& candidates, int idx, vector<int>& cur_vec, int cur_sum, int target) {
	if (cur_sum > target)
		return;
	if (cur_sum == target) {
		ans.push_back(cur_vec);
		return;
	}

	for (int i = idx; i < candidates.size(); i++) {
		cur_vec.push_back(candidates[i]);
		recursiveSearch(ans, candidates, i + 1, cur_vec, cur_sum + candidates[i], target);
		cur_vec.pop_back();

		while (i < candidates.size() - 1 && candidates[i] == candidates[i + 1])
			i++;
	}
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
	sort(candidates.begin(), candidates.end());

	vector<vector<int>> ans;
	vector<int> tmp;
	recursiveSearch(ans, candidates, 0, tmp, 0, target);
	return ans;
}