꼽행착오

두 수 dividend, divisor 가 주어졌을 때 dividend 를 divisor 로 나눈 몫을 구하는 문제

몫을 구하는 문제이기 때문에 나눗셈을 수행하지 않고, 뺄셈으로 나눗셈을 구현하는 방법을 생각해 보았다.

예를 들어, 10 을 3으로 나누면 10 / 3 = 3.333... 이지만 몫만 구할 경우 10 = 3 x 3 이므로 10 = 3 x (2 + 1) 로 표현이 가능하다. 마찬가지로 72 를 7로 나누면 72 / 7 = 10 (몫만) 이고, 72 = 7 x 10 = 7 x (8 + 2) 로 표현이 가능하다.

이처럼 뺄셈으로 표현하기 위해서 divisor 와 2의 승수를 곱한 값을 dividend 에서 빼 나가는 방식으로 문제를 풀이했는데 c++ 에서 int 자료형의 표현 범위로 인한 오류가 발생해서 이는 따로 예외처리 하도록 했다.

위의 풀이로 작성한 코드는 다음과 같다.

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;
        if (divisor == 1)
            return dividend;
        bool neg = (dividend >> 31) ^ (divisor >> 31);
        long dvd = abs(dividend), dvs = abs(divisor);
        int ans = 0;
        while (dvd >= dvs){
            long tmp = dvs, m = 1;
            while ((tmp << 1) <= dvd){
                tmp <<= 1;
                m <<= 1;
            }
            dvd -= tmp;
            ans += m;
        }
        return (neg ? -ans : ans);
    }
};

리스트가 주어졌을 때, 리스트의 노드 k 개씩을 묶어 순서를 반전시키는 문제

리스트 노드들은 다음과 같이 주어진다.

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

리스트를 순차적으로 탐색하면서 매 그룹의 k 번째마다 앞의 노드와 값을 바꾸면 간단히 해결할 수 있다. 하지만 리스트 노드에 이전 노드를 참조하는 포인터 변수는 없기 때문에 이와 같은 방법은 사용이 불가능했다.

마찬가지로 순차적으로 탐색하면서 노드가 가진 값의 순서를 바꿔주는 방법을 생각하다 저장 순서가 서로 다른 스택과 큐를 활용할 수 있겠다는 생각을 했다. 앞에서부터 탐색을 하며 스택에 노드 주소를, 큐에 노드가 가진 값을 저장하고, 스택의 원소 개수가 k 개가 되면 스택과 큐에서 순서대로 노드 주소와 값을 꺼내서 서로를 매칭시켜주면 k 개의 순서를 바꿀 수 있게 된다.

위와 같은 풀이로 작성한 코드는 다음과 같다.

class Solution {
public:
    stack<ListNode*> nodeStack;
    queue<int> numQueue;
    ListNode* reverseKGroup(ListNode* head, int k) {
        for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next){
            numQueue.push(tmp->val);
            nodeStack.push(tmp);
            if (nodeStack.size() == k){
                while (nodeStack.size()){
                    nodeStack.top()->val = numQueue.front();
                    nodeStack.pop();
                    numQueue.pop();
                }
            }
        }
        return head;
    }
};

Valid Number 는 주어진 문자열이 문제의 조건에 맞는 지 확인하는 문제이다.

문제에서 주어진 확인해야 하는 조건은 다음과 같다.

1. 전체 문자열이 Decimal Number / Integer 로 구성되었는가.

(Optional) 지수 표현을 위한 'e' / 'E' 가 등장했을 때 해당 문자 뒤로 Integer 가 나타나는가.

2. Decimal Number 는 부호('+' / '-') 와 소수로 주어진다. 소수는 다음의 3가지 포맷 중 하나이다.

2-1. 하나 이상의 Digit 과 소수점 ex) "2."

2-2. 소수점과 하나 이상의 Digit ex) ".2"

2-3. 하나 이상의 Digit 과 소수점, 그리고 다시 하나 이상의 Digit ex) "2.2"

3. Integer 는 부호('+' / '-') 와 하나 이상의 Digit 으로 이루어진다.

이 조건을 모두 만족하면 함수의 결과값으로 true 를 반환하고, 만족하지 못할 경우 false 를 반환한다.

문제의 해결 방식은 지수 표현을 위한 부분과 그렇지 않은 부분을 나눠서 조건을 검사하는 것이었다.

우선, 문자열의 시작부터 탐색을 하며 문자열이 Sign 과 Digit 으로만 이루어져 있는지를 확인한다.

이 때 Dot 이 문자열에 등장한 경우 Dot 의 개수를 저장해 놓는다. 하나의 Valid Number 가 가질 수 있는 Dot 의 개수는 한 개이다.

또한 지수 문자 'e' / 'E' 가 등장하기 전까지 Digit 의 개수가 최소 1개는 등장해야 하므로 이를 확인한다.

지수 표현을 위한 부분은 위와 유사하게 지수 문자 'e' / 'E' 의 뒤에 Digit 만이 존재하고, Digit 이 한 개 이상 존재하는 지를 확인한다.

마지막으로 Index 가 문자열의 끝에 도달했는 지를 확인하면 주어진 문자열이 Valid Number 인지 확인할 수 있다.

소스 코드는 다음과 같다.

class Solution {
public:
    bool isDecimal(char c) {
        return c >= '0' && c <= '9';
    }

    bool isSign(char c) {
        return c == '+' || c == '-';
    }

    bool isNumber(string s) {
        int i = 0;
        while (s[i] == ' ')
            i++;
        if (isSign(s[i]))
            i++;

        int decimal = 0, dot = 0;
        while (isDecimal(s[i]) || s[i] == '.'){
            if (s[i] == '.'){
                dot++;
            } else {
                decimal++;
            }
            i++;
        }

        if (dot > 1 || decimal < 1)
            return false;

        if (s[i] == 'e' || s[i] == 'E'){
            i++;
            if (isSign(s[i]))
                i++;

            decimal = 0;
            while (isDecimal(s[i])){
                decimal++;
                i++;
            }

            if (decimal < 1)
                return false;
        }

        return s[i] == '\0';
    }
};

# 62. Unique Paths

M * N 크기의 Grid 가 주어졌을 때, Top-Left 부터 Bottom-Right 위치까지 이동하는 유일한 경로의 개수를 구하는 문제

* 이동은 Right, Bottom 방향으로만 가능하다.

오른쪽과 아래로만 이동이 가능하기 때문에 한 위치에서 오른쪽 위치 (몇 번을 이동하든) 로 가는 경로는 하나이고, 아래 방향도 마찬가지이다.

대각선 방향으로 이동하는 것은 오른쪽 -> 아래 / 아래 -> 오른쪽 의 경로만 존재하기 때문에 대각선 방향으로 이동하는 경우는 해당 위치의 바로 위칸까지 이동하는 경로 개수 + 왼쪽 위치로 이동하는 경로 개수로 구할 수 있다.

int uniquePaths(int m, int n) {
	int matrix[101][101] = { 0, };

	for (int j = 0; j < n; j++)
		matrix[0][j] = 1;

	for (int i = 1; i < m; i++) {
		matrix[i][0] = 1;
		for (int j = 1; j < n; j++) {
			matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
		}
	}
	return matrix[m - 1][n - 1];
}

# 63. Unique Paths II

위의 문제와 마찬가지로 M * N 크기의 Grid 가 주어지고 유일한 경로의 개수를 구하는 문제이다.

유일한 차이는 중간에 장애물이 있어 해당 칸으로는 이동이 불가능하다는 점이다.

# 62. 와 풀이는 동일하게 진행하지만, 장애물이 있는 경우는 해당 칸으로 이동하는 경로의 개수를 0으로 만든다.

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	int M = obstacleGrid.size(), N = obstacleGrid[0].size();
	if (obstacleGrid[0][0] == 1 || obstacleGrid[M - 1][N - 1] == 1)
		return 0;
	vector<vector<int>> ans(M, vector<int>(N, 0));
	for (int k = 0; k < N; k++) {
		if (obstacleGrid[0][k] != 1)
			ans[0][k] = 1;
		else
			break;
	}

	for (int i = 1; i < M; i++) {
		if (obstacleGrid[i][0] != 1)
			ans[i][0] = ans[i - 1][0];
		else
			ans[i][0] = 0;
		for (int j = 1; j < N; j++) {
			if (obstacleGrid[i][j] == 1)
				ans[i][j] = 0;
			else
				ans[i][j] = ans[i][j - 1] + ans[i - 1][j];
		}
	}
	return ans[M - 1][N - 1];
}

# 64. Minimum Path Sum

M * N Grid 가 주어지고 각각의 칸에는 임의의 값이 들어있을 때 Top-Left 칸에서 Bottom-Right 칸으로 이동할 때 가장 작은 합을 갖는 경로의 합을 찾는 문제

* 위와 마찬가지로 이동은 오른쪽 / 아래 방향으로만 가능하다.

우선 M * N 크기의 행렬을 만들고, 각 칸 별로 최소 합을 만드는 경로를 찾도록 했다.

경로는 위의 문제에서 구했듯 어떤 한 위치로 이동할 수 있는 경우는 해당 위치의 윗칸 / 왼쪽 칸에서 해당 칸으로 이동하는 방법밖에 존재하지 않는다.

따라서 어떤 위치까지 경로의 합의 최소값은 윗칸 / 왼쪽 칸까지의 합 중 작은 값 + 현재 칸의 값이 될 것이다.

int minPathSum(vector<vector<int>>& grid) {
    int N = grid.size(), M = grid[0].size();

    for (int i = 1; i<M; i++)
        grid[0][i] += grid[0][i-1];
    for (int i = 1; i<N; i++)
        grid[i][0] += grid[i-1][0];

    for (int i = 1; i<N; i++){
        for (int j = 1; j<M; j++){
            grid[i][j] += (grid[i-1][j] < grid[i][j-1] ? grid[i-1][j] : grid[i][j-1]);
        }
    }
    return grid[N-1][M-1];
}

# 58. Length of Last Word

주어진 문자열 (문장) 에서 마지막 단어의 길이를 구하는 문제

간단하게 C++ 의 String 내장 메소드 find_last_of / find_last_not_of 를 사용해 문제 해결

int lengthOfLastWord(string s) {
	if (s.find_first_not_of(" ") == -1)
		return 0;
	int last = s.find_last_not_of(" ");
	int first = s.substr(0, last).find_last_of(" ");
	return last - first;
}

# 59. Spiral Matrix II

정수 N 이 주어졌을 때, N * N 크기의 Spiral Matrix 를 만드는 문제

Spiral Matrix 의 값이 증가하는 방향 순서대로 증가하는 값을 넣어주도록 했다.

int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };

    vector<vector<int>> generateMatrix(int n) {
	vector<vector<int>> ans(n, vector<int>(n, 0));
	int dir = 0, cy = 0, cx = 0;
	int max_val = n * n;
	for (int i = 1; i <= max_val; i++) {
		ans[cy][cx] = i;
		int ny = cy + dy[dir], nx = cx + dx[dir];
		if ((ny < 0 || ny >= n || nx < 0 || nx >= n) || ans[ny][nx] != 0) {
			dir = (dir + 1) % 4;
			ny = cy + dy[dir], nx = cx + dx[dir];
		}
		cy = ny, cx = nx;
	}
	return ans;
}

# 61. Rotate List

List 의 Head 가 주어지고, 정수 k 가 주어졌을 때 k 번만큼 오른쪽으로 회전한 리스트를 구하는 문제

처음 생각한 해결 방법은, List 의 tail 부터 탐색해서 해당 node 의 next 링크를 head 로 연결하고 해당 node 를 head 로 변경하는 것이었는데 이 방법은 List 에서 prev link 를 구할 수 없어 구현이 불가했다.

때문에 다시 생각해 낸 방법은, head 부터 끝까지 탐색하면서 각각 node 들이 저장하고 있는 값들을 구하고 그 값을 다시 node 에 순서를 변경해 저장하는 것이었다.

ListNode* rotateRight(ListNode* head, int k) {
	int val[501];
	int size = 0;
	for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
		val[size++] = tmp->val;
	}
	if (size <= 1)
		return head;
	k %= size;
	int idx = (size - k) % size;
	for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
		tmp->val = val[idx];
		idx = (idx + 1) % size;
	}
	return head;
}

# 55. Jump Game

배열이 주어지고 배열의 각 값이 해당 위치에서 다음 인덱스로 Jump 가능한 범위라고 할 때 시작 인덱스부터 마지막 인덱스까지 점프가 가능할 지를 찾는 문제

이 문제는, 시작 인덱스부터 탐색을 하면 각 인덱스에서 점프를 뛰어 갈 수 있는 위치를 일일히 표시해야 해서 시간이 오히려 오래 걸리는 문제였다.

문제 해결이 안 되는 것은 아니지만, 이보다 빠르게 해결할 수 있는 방법이 끝 인덱스부터 탐색을 하는 방법이었다.

뒤에서부터 앞으로 탐색을 하면서 현재 위치에서 내가 저장하고 있는 위치까지 점프를 뛸 수 있으면, 저장하고 있는 위치를 현재 위치로 바꾼 다음 다시 앞으로 탐색을 진행하는 방식이다.

이 방식을 통해 O(N) 으로 탐색이 가능해졌고 문제의 해결을 빠르게 할 수 있었다.

bool canJump(vector<int>& nums) {
	int last = nums.size() - 1;
	for (int i = last - 1; i >= 0; i--) {
		if (i + nums[i] >= last) {
			last = i;
		}
	}
	return (last == 0);
}

# 56. Merge Intervals

Interval 들을 저장하는 배열이 주어졌을 때, 겹치는 Interval 들을 합치는 문제

일단 이 문제를 해결하기에 앞서 Interval 들이 서로 겹쳐지는 지를 확인하기 위해서 배열을 정렬을 한 후 문제를 해결했다.

결과를 저장할 배열을 새로 만들고, 앞에서부터 Interval 이 겹쳐지면 겹쳐진 범위의 최대를 저장하는 식으로 문제를 풀었다.

vector<vector<int>> merge(vector<vector<int>>& intervals) {
	sort(intervals.begin(), intervals.end());

	vector<vector<int>> ans;
	ans.push_back(intervals[0]);

	for (int i = 1; i < intervals.size(); i++) {
		if (ans.back()[1] >= intervals[i][0]) {
			ans.back()[1] = max(ans.back()[1], intervals[i][1]);
		}
		else {
			ans.push_back(intervals[i]);
		}
	}
	return ans;
}

# 57. Insert Intervals

겹치지 않는 Interval 들이 주어졌을 때, 새로운 Interval 을 삽입하는 문제

기존에 있던 Interval 에 겹쳐지는 영역이 있을 수 있기 때문에 해당 부분에 대한 처리가 필요한 문제였다.

새로운 Interval 과 겹치는 Interval 전까지는 그대로 저장하고, 겹치는 Interval 들에 대해서 하나의 Interval 로 만든 다음 해당 Interval 을 결과에 저장하고 남은 Interval 들을 저장하도록 해서 문제를 해결했다.

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
	vector<vector<int>> ans;

	int idx = 0;
	while (idx < intervals.size() && intervals[idx][1] < newInterval[0])
		ans.push_back(intervals[idx++]);

	while (idx < intervals.size() && intervals[idx][0] <= newInterval[1]) {
		newInterval[0] = min(newInterval[0], intervals[idx][0]);
		newInterval[1] = max(newInterval[1], intervals[idx][1]);
		idx++;
	}
	ans.push_back(newInterval);
	while (idx < intervals.size())
		ans.push_back(intervals[idx++]);

	return ans;
}

# 50. Pow(x, n)

x^n 을 구하는 문제

단순히 x 를 n 번 곱해서 문제를 해결할 수도 있지만, 그렇게 해결할 경우 n 이 INT_MIN ~ INT_MAX 범위를 갖기 때문에 시간초과가 날 것으로 생각된다.

때문에 이 방식이 아니라 조금 더 현명하게 문제를 해결하고자 한 방법이 이진법을 생각한 것이었다. 이진법의 경우, 각 자릿수가 2의 승수를 의미하는데 (네 자리라면 8, 4, 2, 1 이런식으로) 각 자리별로 bit 가 1이면 해당 값을 더하고, 0이면 패스하는 식으로 이루어진다.

이 문제는 x 의 n 승을 구하는 문제이므로 더하는 게 아니라 해당 값을 곱하는 방식으로 문제를 풀었다.

추가로, 처음에는 n 이 음수일 경우 값을 나눠주도록 해서 문제를 해결하려 했는데 일반적으로 곱셈보다 나눗셈이 더 시간이 많이 걸린다는 사실을 알지 못했다. 그래서 시간초과가 발생하는 걸 보고, 우선 값을 다 곱해준 뒤 나누기를 해 주는 방식으로 문제를 해결했다.

double myPow(double x, int n) {
    double ans = 1;
    bool neg = n < 0;

    while (n){
        if (n & 1)
            ans *= x;
        x *= x;
        n /= 2;
    }

    if (neg){
        ans = 1 / ans;
    }
    return ans;
}

# 53. Maximum Subarray

배열이 주어졌을 때, 해당 배열의 연속된 SubArray 중 가장 큰 합을 갖는 경우의 합을 구하는 문제

DP 의 대표적인 유형 문제로, 배열을 순차 탐색하면서 (이전 인덱스까지의 최대 합 + 현재 인덱스의 값) 과 (현재 인덱스의 값) 을 비교해 더 큰 값을 저장해 나가는 방식으로 문제를 해결했다.

int maxSubArray(vector<int>& nums) {
    if (nums.size() == 1)
        return nums[0];
    int max_sum = nums[0];
    int cur_sum = nums[0];

    for (int i = 1; i<nums.size(); i++){
        cur_sum = max(cur_sum + nums[i], nums[i]);
        max_sum = max(max_sum, cur_sum);
    }
    return max_sum;
}

# 54. Spiral Matrix

M * N 행렬이 주어졌을 때, 해당 행렬을 나선형으로 탐색한 결과를 구하는 문제

이 문제는, BFS 문제를 풀 때 주로 사용한 방식으로 문제를 해결했다.

{오른쪽, 아래, 왼쪽, 위} 방향으로 이동할 때의 인덱스 변화량을 미리 저장해 두고 방향만 바꾸는 방식으로 순서대로 탐색을 했다.

이미 탐색한 위치인 경우, 값을 INT_MIN 값으로 바꿔주어서 다시 탐색하지 않도록 하고 행렬의 범위를 벗어나는 경우 방향을 바꾸도록 했다.

int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };

vector<int> spiralOrder(vector<vector<int>>& matrix) {
	int dir = 0, cy, cx;
	int n = matrix.size(), m = matrix[0].size();
	int size = n * m;
	vector<int> ans;
	cy = cx = dir = 0;
	while (size--) {
		ans.push_back(matrix[cy][cx]);
		matrix[cy][cx] = INT_MIN;
		int ny = cy + dy[dir], nx = cx + dx[dir];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m) {
			dir = (dir + 1) % 4;
			ny = cy + dy[dir], nx = cx + dx[dir];
		}
		else if (matrix[ny][nx] == INT_MIN) {
			dir = (dir + 1) % 4;
			ny = cy + dy[dir], nx = cx + dx[dir];
		}
		cy = ny, cx = nx;
	}
	return ans;
}

# 47. Permutations II

# 46. 과 유사하지만, 주어진 배열에 중복값이 있을 수 있어 Unique 한 순열을 찾기 위한 조건이 하나 추가된 문제

배열에 중복값이 존재하기 때문에, 배열을 우선 정렬을 하고 문제 풀이를 시작했고,

앞서 DFS 방식으로 문제를 해결한 부분에 추가적으로 적용한 조건이 이미 해당 위치에서 사용한 값은 넘기도록 하는 조건을 추가했다.

void recursivePermutation(vector<vector<int>>& ans, vector<int>& nums, vector<int>& cur, bool used[]){
    if (nums.size() == cur.size()){
        ans.push_back(cur);
        return;
    }
    int prev = -30;

    for (int i = 0; i<nums.size(); i++){
        if (used[i])
            continue;
        if (prev != -30 && prev == nums[i])
            continue;
        prev = nums[i];
        used[i] = true;
        cur.push_back(nums[i]);
        recursivePermutation(ans, nums, cur, used);
        cur.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    vector<int> vec;
    bool used[10];
    recursivePermutation(ans, nums, vec, used);

    return ans;
}

# 48. Rotate Image

주어진 Matrix 를 우측으로 90도 회전하는 문제

이 문제는, 처음 마주했을 때 그 위치를 어떻게 계산해서 바꿔줄까를 고민하고 있었는데 그러던 중 Solution 을 보고 그 방법이 너무 간단해서 그 방법대로 문제를 해결하게 되었다.

어떤 행렬을 우측으로 90도 회전하는 것은, 그 행렬의 전치행렬을 구하고 col 을 reverse 하게 되면 우측으로 90도 회전한 것과 같아진다는 것이 그 방법이었다.

void rotate(vector<vector<int>>& matrix) {
    int n = matrix[0].size();

    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            swap(matrix[i][j], matrix[j][i]);
        }
    }
    for (int j = 0; j < (n + 1) / 2; j++){
        for (int i = 0; i<n; i++){
            swap(matrix[i][j], matrix[i][n - j - 1]);
        }
    }
}

# 49. Group Anagrams

문자열 배열이 주어졌을 때, 문자열들을 Anagram* 끼리 그룹을 묶어 주는 문제

* Anagram 이란, 문자열에 속한 문자들이 같은 경우를 Anagram 이라 한다.

이 문제는, 해시테이블을 활용하면 쉽게 해결할 수 있을 거라 생각했다.

우선, 각 문자열들이 동일한 문자를 갖는 지를 확인하기 위한 방법으로 각각의 문자열들을 정렬하고, 정렬된 문자열을 Key 로 리스트에 저장하는 방식으로 문제를 해결했다.

최종적으로는 해시테이블을 벡터로 변환해서 Return 해서 문제를 간단하게 해결했다.

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    map<string, vector<string>> table;

    for (string str : strs){
        string sorted = str;
        sort(sorted.begin(), sorted.end());

        map<string, vector<string>>::iterator it = table.find(sorted);
        if (it != table.end()){
            // Sorted String 을 Key 로 갖는 List 가 있을 때
            it->second.push_back(str);
        }
        else {
            vector<string> v = {str};
            table.insert(make_pair(sorted, v));
        }
    }
    vector<vector<string>> ans;
    for(map<string, vector<string>>::iterator it = table.begin(); it != table.end(); it++){
        ans.push_back(it->second);
    }
    return ans;
}

# 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;
}

# 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;
}