Pramp - Array of Array Products
문제
배열이 주어진다. 자기자신을 제외한 나머지 배열을 모두 곱한 값으로 변환해라. (단, 나눗셈을 사용할 수 없다)
input: arr = [8, 10, 2]
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10]
input: arr = [2, 7, 3, 4]
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]Leetcode 에서 이 문제와 동일: Leetcode - 238. Product of Array Except Self
후기
- brute force -> O(n^2)
- O(n)
- all = multiply all
- for -> arr[i] = all / arr[i];
여기까지는 풀어본 문제라서 쉽게 해결책을 떠올릴 수 있었다. 그런데 나눗셈을 사용했으므로 안됨. 다른 해결책을 사용해야하는데 잘 떠올리지 못함. 힌트를 two pass 로 풀어보라고 받았는데, 그래도 해결책을 잘 떠올리지 못했다. (각각의 값을 곱한것까지는 함. 그 이상 못함). 해결 아이디어를 더 받아서 꾸역꾸역 풀긴했는데 배열인덱싱이 복잡해서 완벽하게 풀지 못함. (그리고 벡터에서 런타임 에러가 발생).
이런 배열 인덱싱 문제는 반드시 [인덱스] 별로 직접 써보면서 따라가자. 머리로만 풀면 절대 안됨.
하지만 긍정적인 부분은 긴장을 전보다 훨씬 덜 했다는것. 막힐때 잘안풀릴때 더 초초하고 긴장하기 마련인데 이번엔 거의 긴장을 안했다. 계속 물어보고 생각을 계속 이야기했다. -> 많이 좋아진 부분!.
이거 못푼다고 내 인생이 망하는것도 아니고 걍 즐기자 ㅋㅋ
해결 아이디어
배열의 크기가 총 4일때, 최종 정답은 아래와같은 인덱스의 곱이 된다.
res[] [1]*[2]*[3] [0]*[2]*[3] [0]*[1]*[3] [0]*[1]*[2]1부터 시작해 인덱스를 왼쪽에서 오른쪽으로 하나씩 곱하고, 그뒤에 맨마지막부터 1부터 시작해 오른쪽에서 왼쪽으로 하나씩 곱하면 아래와 같은 형태가 된다.
l->r: 1 1*[0] 1*[0]*[1] 1*[0]*[1]*[2]
l<-r: *[3]*[2]*[1] *[3]*[2] *[3] 1그리고 위 아래를 곱하면 res[] 답이된다!
예를 들어 아래와 같이 입력이 주어지면
arr = [2 7 3 4]첫번째로 left -> right 로 하나씩 곱한다. 주의할 점은 리턴배열 res[]에 맨처음에는 1을 저장하고, 그뒤 [0] 부터 [2] 까지만 곱하는것. 그럼 [3] 인덱스 값이 arr[0] * arr[1] * arr[2] 곱한 값이 된다. 그러면 res[] 마지막 인덱스의 답(42)은 계산이 완료된 상태
res = [7*3*4 2*3*4 2*7*4 2*7*3]
[1 1*2 1*2*7 1*2*7*3] 이제 right -> left순으로 계산한다.
res = [7*3*4 2*3*4 2*7*4 2*7*3]
[1 1*2 1*2*7 1*2*7*3] (left -> right)
1*7*3*4 1*3*4 1*4 1 (right -> left)최종 아래와 같이 정답이 계산된다. 어렵지만 기발한 아이디어 ㅇㅈ..
res = [7*3*2 2*3*4 2*7*4 2*7*3]대략 이렇게 곱하는 구조.
_____ l->r
arr = [2 7 3 4]
^^^^^ l<-r해결
#include <iostream>
#include <vector>
vector<long> arrayOfArrayProducts(const vector<int>& arr)
{
vector<long> res;
if (arr.size() <= 1)
return res; // return empty vector
res = vector<long>(arr.size(), 0);
int temp = 1;
for (int i = 0; i < arr.size(); i++) {
res[i] = temp;
temp *= arr[i];
}
temp = 1;
for (int i = arr.size() - 1; i >= 0; i--) {
res[i] *= temp;
temp *= arr[i];
}
return res;
}
int main() {
return 0;
}238. Product of Array Except Self
문제
주어진 배열을 자기자신을 제외한 모든 값을 곱한 값으로 바꾸어라.
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]해결
0이 한개일때, 0이 두개일때의 경우를 제외하고 구간합으로 해결할수 있음.
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
*returnSize = numsSize;
int z_cnt = 0;
int prod = 1;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 0) {
z_cnt++;
if (z_cnt > 1)
break;
continue;
}
prod *= nums[i];
}
if (z_cnt == 0) {
for (int i = 0; i < numsSize; i++)
nums[i] = prod / nums[i];
} else if (z_cnt == 1) {
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 0)
nums[i] = prod;
else
nums[i] = 0;
}
} else {
for (int i = 0; i < numsSize; i++)
nums[i] = 0;
}
return nums;
}해결 O(n)
나누기 연산을 사용하지 않는 방법. left -> right 그리고 left <- right 이렇게 two pass로 풀수 있는 신박한 방법 -> 풀이 설명은 여기서 Pramp - Array of Array Products
prod[] [1]*[2]*[3] [0]*[2]*[3] [0]*[1]*[3] [0]*[1]*[2]
l->r: 1 1*[0] 1*[0]*[1] 1*[0]*[1]*[2]
l<-r: *[3]*[2]*[1] *[3]*[2] *[3] 1class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> prod(nums.size(), 0);
int temp = 1;
for (int i = 0; i < nums.size(); i++) {
prod[i] = temp;
temp *= nums[i];
}
// after that prod[last idx] got a answer
temp = 1;
for (int i = nums.size() - 1; i >= 0; i--) {
prod[i] *= temp;
temp *= nums[i];
}
// after that prod[0] ~ prod[last idx -1] got a answer
return prod;
}
};724. Find Pivot Index
문제
특정 index를 기준으로 좌/우 배열값의 합이 동일한 index를 리턴하라.
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11해결 O(N)
brute force로 한다면 (n^2)이 되겠지만. Prefix Sum(구간합 테그닉?)을 사용하면 O(n)에 해결이 가능.
처음에 l_sum/r_sum을 먼저 구해놓고.
배열을 하나씩 순회하면서 아래와같이 현재 index값을 빼거나 더하는 방식으로 l_sum/r_sum을 O(1)에 계산.
- l_sum = l_sum + nums[i - 1]
- r_sum = r_sum - nums[i]
int pivotIndex(int* nums, int numsSize){
int l_sum = 0;
int r_sum = 0;
int pivot = -1;
for (int i = 1; i < numsSize; i++)
r_sum += nums[i];
if (l_sum == r_sum)
return 0;
for (int i = 1; i < numsSize; i++) {
l_sum = l_sum + nums[i - 1];
r_sum = r_sum - nums[i];
if (l_sum == r_sum) {
pivot = i;
break;
}
}
return pivot;
}1652. Defuse the Bomb
문제
주어진 배열값과 k값으로 폭탄을 해체하는 코드를 생성해라. 코드를 생성하는 방법은, 각 자리수를 k개만큼 이전/이후 까지를 더한값으로 계산하면 된다. 아래 예시를 확인!
주의할 사항은 순환배열이라는 사실.
Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers.
The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1].
Notice that the numbers wrap around.
Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4].
Notice that the numbers wrap around again.
If k is negative, the sum is of the previous numbers.https://leetcode.com/problems/defuse-the-bomb/
해결 O(n)
sliding window 구간합 문제, 매번 모든 구간을 더할필요없고 이전 sum에서 필요한 부분만 더하고 빼면 O(1) 에 합을 계산할 수 있다. 배열인덱싱은 항상 햇갈린다. 이번 문제는 인덱싱이 복잡해서 더 햇갈렸음.
배운것들.
- 순환(circular)하는 배열 -> 이런 단어가 나오면 항상
%으로 배열인덱싱을 한다. - 시계방향 순환 인덱싱:
[i % asize]/ 반 시계방향 순환 인덱싱:?. (asize 배열크기) - 이 문제의 경우 k가 음수/양수이건간에 시계방향 순환 인덱싱이기 때문에
[positino % asize]으로 적절한 포지션을 계산한 뒤% 크기연산을 하면 된다.
k < 0인경우 position 구하는 계산이 매우 햇갈렸다. 근데 생각해보면 시계방향으로 커지는것이기 때문에 그냥 적절한 position만 계산한다는 생각을 하면 될것같다.[((codeSize + k - 1) + i) % codeSize]
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* decrypt(int* code, int codeSize, int k, int* returnSize){
int sum = 0;
*returnSize = codeSize;
int *ret = (int *)calloc(codeSize, sizeof(int));
if (k == 0) {
return ret;
} else if (k > 0) {
for (int i = 1; i < k + 1; i++)
sum += code[i]; // no need to [i % codeSize]
ret[0] = sum;
for (int i = 1; i < codeSize; i++) {
sum = sum - code[i] + code[(i + k) % codeSize];
ret[i] = sum;
}
} else if (k < 0) {
for (int i = codeSize - 1; i >= codeSize + k; i--)
sum += code[i]; // no need to [i % codeSize]
ret[0] = sum;
for (int i = 1; i < codeSize; i++) {
sum = sum - code[((codeSize + k - 1) + i) % codeSize] + code[(i-1) % codeSize];
ret[i] = sum;
}
}
return ret;
}346. Moving Average from Data Stream
문제
입력이 아래와같이 주어진다. 이동평균(moving average) 크기가 주어지고, 값이 계속 추가될때 마다 moving average 크기만큼의 평균을 구하라.
Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]
Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3https://leetcode.com/problems/moving-average-from-data-stream/
해결 O(1) / O(N)
구간합을 활용해 매번 size 만큼 더해서 평균을 내지 않고 O(1)만에 계산. next함수의 최대 호출 갯수인 10001개만큼의 배열을 할당해야했다.
#define DATA_SIZE 10001
typedef struct {
int cur_size;
int size;
int idx;
int total;
int *data;
} MovingAverage;
MovingAverage* movingAverageCreate(int size) {
MovingAverage *obj = malloc(sizeof(MovingAverage));
obj->total = 0;
obj->size = size;
obj->cur_size = 0;
obj->idx = 0;
obj->data = (int *)calloc(DATA_SIZE, sizeof(int));
return obj;
}
double movingAverageNext(MovingAverage* obj, int val) {
int sum = 0;
if (obj->cur_size < obj->size)
obj->cur_size++;
obj->data[obj->idx] = val;
if (obj->idx - obj->size < 0)
sum += obj->total + obj->data[obj->idx];
else
sum += obj->total - obj->data[obj->idx - obj->size] + obj->data[obj->idx];
obj->total = sum;
obj->idx++;
return (double)sum / obj->cur_size;
}
void movingAverageFree(MovingAverage* obj) {
free(obj->data);
free(obj);
}
