알고리즘 정리
간단한 투포인터의 정의
투 포인터는 말 그대로 두 개의 포인터를 조작해서 원하는 결과를 찾는것을 말합니다.
1차원 배열에서 주로 사용되며 포인터를 어디에 배치하고 언제 증가, 감소 시킬지가 중요한 기법입니다.
오름차순으로 정렬되어 있는 배열에서
제곱값의 순서로 정렬해야하지만, O(N)으로 정렬해야 하는 문제입니다.
var sortedSquares = function(nums) {
let left = 0;
let right = nums.length - 1;
const answer = []
while (left < right) {
const leftNum = nums[left] ** 2;
const rightNum = nums[right] ** 2;
if (leftNum > rightNum) {
answer.push(leftNum)
left++;
}
else {
answer.push(rightNum);
right--;
}
}
answer.push(nums[right] ** 2)
return answer.reverse()
};처음 시도해서 Accept 받았던 코드입니다.
left와 right의 index를 가지는 nums 배열 값을 제곱한 뒤에
서로 비교 후 큰 값을 answer 배열에 push 합니다.
이후 answer 배열을 뒤집어서 return 합니다.
O(2N)으로 상수항은 없어지므로 O(N)이 되기는 하지만,
마지막에 뒤집어서 return 하는 점이 깔끔하지 못하다 생각해
조금 더 고민해보고 답을 찾아냈습니다.
var sortedSquares = function(nums) {
let left = 0;
let right = nums.length - 1;
const answer = new Array(nums.length);
for (let index = nums.length - 1; index >= 0; index--) {
const leftNum = nums[left] ** 2;
const rightNum = nums[right] ** 2;
if (leftNum > rightNum) {
answer[index] = leftNum;
left++;
}
else {
answer[index] = rightNum;
right--;
}
}
return answer;
};다시 한 번 생각을 해보니 배열을 앞에서 넣지 않는다면 뒤집을 필요가 없었습니다.
따라서 새로운 배열을 nums의 길이 만큼 선언해준뒤에,
뒤에서부터 비교한 값을 넣어주기만 하면 된다고 생각했고,
Accept를 받을 수 있었습니다.
다시 풀어야할 문제
도대체 이게 왜 투포인터일까? 를 가장 많이 고민한 문제였습니다.
문제 조건인 공간복잡도 O(1)을 지키려다 보니 꽤 어려웠습니다.
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const reverse = (nums, start, end) => {
while (start < end) {
[nums[start], nums[end]] = [nums[end], nums[start]];
start++;
end--;
}
return nums;
}
const rotate = (nums, k) => {
const length = nums.length;
const rotateCount = k % length;
if (rotateCount === 0) {
return;
}
reverse(nums, 0, length - 1);
reverse(nums, 0, rotateCount - 1);
reverse(nums, rotateCount, length - 1);
}시간이 많이 걸린 이유는, 먼저 문제 조건을 제대로 보지 못한점입니다.
리트코드에서는 코드 위에 조건을 달아주기도 하는데,
Do not return anything, modify nums in-place instead.
아주 친절하게 달아줬지만 신경을 못 써버렸네요...
이 문제가 투포인터인 이유는 reverse 함수를 사용하지 못하기 때문인것 같습니다.
문제를 풀 때 바꿔야 할 위치를 정해줘야 하기 때문에 start, end를 통한
배열 뒤집기를 진행했는데 이를 투포인터로 해결했습니다.
k 값이 커질 수 있지만,
6의 길이를 가진 배열을 6번 돌리나 12번 돌리나 18번 돌리나 똑같기 때문에
미리 k 값을 배열의 길이로 나눈 나머지로 정해놓고 진행하면
보다 빠르게 구하는것이 가능합니다.
또 한번 다시 풀어보면 좋은 문제
문제가 짧을수록 풀기가 너무 어려운것 같습니다..ㅠ-ㅠ
앞에 있는 0들을 냅다 맨 뒤에다가 넣으면 되는 문제이지만,
역시나 새로운 공간을 만들지 못하는 in-place 문제입니다.
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let left = 0;
let right = 0;
while (left < nums.length && right < nums.length) {
if (nums[left] !== 0) {
left++;
right = left;
continue;
}
right++;
if (nums[right] && nums[right] !== 0) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
}
}
};저는 0이 나오는 가장 첫 번째 위치를 주목했습니다.
left는 0이 가장 먼저 나오는 index로 만들었고,
right는 left의 뒤에 있는 값들중 0이 아닌 값의 index로 만들었습니다.
이후 만약 0이 아니라면 swap을 진행하면서 left와 right 값을 증가시켜 나갑니다.
객체로 풀었던 two-sum1 문제와 비슷한 two-sum2 문제입니다.
이번에는 index를 return 해야하는 문제입니다.
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let start = 0;
let end = numbers.length - 1;
while (true) {
const sum = numbers[start] + numbers[end];
if (sum === target) {
return [start + 1, end + 1];
}
if (sum < target) {
start++;
}
else {
end--;
}
}
};전형적인 two-pointer 문제였던것 같습니다.
풀이는 생략합니다!
이 친구도 생략!
이 친구는 안 생략..
단순히 문자열을 뒤집어서 return 하는 문제가 아닌 공백도 포함해야 하는 문제입니다.
중요한것은 공백을 뒤집어버리면 안 된다는 점입니다.
/**
* @param {string} s
* @return {string}
*/
const reverse = (string) => {
const splitedString = string.split('');
let start = 0;
let end = string.length - 1
while (start < end) {
[splitedString[start], splitedString[end]] = [splitedString[end], splitedString[start]];
start++;
end--;
}
return splitedString.join('');
}
var reverseWords = function(s) {
return s.split(' ').map(str => reverse(str)).reduce((acc, cur, index) => {
index !== 0 ? acc += ' ' + cur : acc += cur;
return acc;
}, '');
};일단 reverse 함수를 만들어 문자열을 뒤집어줍니다.
이후에 map을 통해 모든 원소에 reverse 함수를 적용시켜준 뒤
reduce를 통해 만약 인덱스가 0이 아닌 경우 앞에 공백을 붙여서 return 해줍니다.
오늘의 배운점
- 오랜만에 reduce를 사용해보았읍니다..^^
- 투포인터를 다시 복습해보았읍니다.. ^^
- 흥분해서 3일치 문제를 풀어버렸읍니다.. ^^
