[LeetCode # 50, 53, 54] 문제 풀이

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