[LeetCode # 43, 45, 46] 문제 풀이

# 43. Multiply Strings

정수를 표현하는 문자열 2개가 주어졌을 때, 해당 정수들의 곱을 구하는 문제

정수형으로 표현 가능한 범위를 초과하기 때문에 타입 변환 후 곱셈을 수행하는 방식으로는 해결이 불가능

 

해당 문제를 보고 처음 든 생각은, 처음 곱셈을 배울 때 한자리씩 곱셈을 수행하고 그 결과를 더하는 방식이었다.

문자열이기 때문에 곱셈을 수행할 수는 없고, 한 자리씩 수행을 한다면 문제를 해결할 수 있을 것이라 생각했다.

하지만 단순히 이런 방식으로는 문제 해결이 불가능했고(시간 초과), 다소 최적화가 필요한 부분이 있어 해당 부분을 적용했다.

최적화를 한 방식은, 두 수를 곱했을 때 결과로 나올 수 있는 자리수는 두 자리수의 합이기 때문에 미리 문자열을 해당 사이즈만큼 선언해 놓고 그 문자열에 값을 더하는 방식으로 문제를 해결하는 것이었다.

 

string multiply(string num1, string num2) {
	string sum(num1.size() + num2.size(), '0');

	for (int i = num1.size() - 1; i >= 0; i--) {
		int carry = 0;
		for (int j = num2.size() - 1; j >= 0; j--) {
			int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
			sum[i + j + 1] = tmp % 10 + '0';
			carry = tmp / 10;
		}
		sum[i] += carry;
	}

	int startpos = sum.find_first_not_of("0");
	if (startpos != string::npos)
		return sum.substr(startpos);
	return "0";
}

# 45. Jump Game II

0 이 아닌 수들로 이루어진 배열이 주어졌을 때, 최소한의 점프* 로 마지막 인덱스에 도달할 수 있는 점프 횟수를 구하는 문제

* 각 배열의 값들은 해당 위치에서 점프를 뛸 수 있는 최대 거리

 

이 문제는 전형적인 DP 문제라고 생각하고 문제를 해결했다.

시작 인덱스부터 탐색을 해나가며 각 인덱스 위치에서 점프를 뛸 수 있는 각각의 인덱스로 점프를 뛰고, 최소한의 점프로 해당 인덱스에 도달한 점프 횟수를 저장하는 방식으로 문제를 풀 수 있었다.

 

int jump(vector<int>& nums) {
    int len = nums.size();
    int ans[1001] = {0, };

    for (int i = 0; i<len; i++){
        for (int k = 1; k <= nums[i] && i + k < len; k++){
            if (ans[i + k] == 0 || ans[i] + 1 < ans[i + k]){
                ans[i + k] = ans[i] + 1;
            }
        }
    }
    return ans[len - 1];
}

# 46. Permutations

정수형 배열이 주어졌을 때, 이 배열로 만들 수 있는 모든 순열을 만드는 문제

 

이 문제는 전형적인 dfs 문제로, 어떤 값이 사용되었는지 사용되지 않았는지를 저장해 나가며 그 값이 사용되지 않은 값이라면 추가하고, 사용된 값이라면 Pass 하는 방식으로 문제를 해결할 수 있었다.

 

void recursivePermutation(vector<vector<int>>& ans, vector<int>& nums, vector<int>& cur, bool used[]){
    if (nums.size() == cur.size()){
        ans.push_back(cur);
        return;
    }
    for (int i = 0; i<nums.size(); i++){
        if (used[i])
            continue;
        used[i] = true;
        cur.push_back(nums[i]);
        recursivePermutation(ans, nums, cur, used);
        cur.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> vec;
    bool used[10];
    recursivePermutation(ans, nums, vec, used);

    return ans;
}