👨💻 CodeKata
이번 주부터 코드카타를 시작했습니다. 두 명씩 짝을 지어 자바스크립트 알고리즘 문제 풀이를 진행합니다. 철저하게 자율학습으로 운영되며 모르는 경우 주말까지 고민해보거나 동기들에게 SOS를 치는 수밖엔 없습니다.
저는 이번에 행운님과 코드카타를 진행하게 되었고, 제가 Navigator 역할을 맡아서 진행하고 있는데 행운님께서 서서히 알고리즘에 재미에 빠지게 되신 거 같아서 기쁠 따름입니다.
다만, 저는 알고리즘이 너무 힘들다는 사실😅 그래도 둘이서 같이 해결해나가니 떠오르지 않던 풀이 방법도 떠오르게 됩니다. 이런 것들이 협업의 중요성이라고 생각합니다. 그럼 서론은 이쯤으로 하고 문제풀이에 대해서 이야기하겠습니다.
🎬 Day1
문제
twoSum함수에 숫자배열과 '특정 수'를 인자로 넘기면,
더해서 '특정 수'가 나오는 index를 배열에 담아 return해 주세요.
nums: 숫자 배열
target: 두 수를 더해서 나올 수 있는 합계
return: 두 수의 index를 가진 숫자 배열
예를 들어,
nums은 [4, 9, 11, 14] target은 13
nums[0] + nums[1] = 4 + 9 = 13 이죠?
그러면 [0, 1]이 return 되어야 합니다.가정
target으로 보내는 합계의 조합은 배열 전체 중에 2개 밖에 없다고 가정하겠습니다.
풀이 (1)
실제로 해당 문제를 보자마자 반복문 중첩에 대해서 생각이 났습니다. 결국, 배열의 두 인덱스를 각각 돌아서 합계를 만들어내야하기 때문에 제일 쉬운 방법이라고 할 수 있습니다.
그러나 아시다시피 이 방법은 시간 복잡도가 O(n²)으로 좋지 않은 풀이방법이라 할 수 있습니다. 속도가 그만큼 느리게 되니까요. 일단, 저희가 해결한 반복문 중첩 풀이 방법입니다.
1 2 3 4 5 6 7 8 9 | const twoSum = (nums, target) => { for (let i = 0; i < nums.length; i++) { for (let j = nums.length - 1; j > i; j--) { if (nums[i] + nums[j] === target) { return [i, j] } } } } | cs |
위와 같이 풀이를 진행했습니다. 코드는 복잡한 것은 없지만, 중첩된 반복문의 조건이 j > i때까지로 [0, 0], [1, 1], [1, 0] 등의 불필요한 반복을 줄이도록 하였습니다. 그러나 위에서 언급했던 것처럼 시간 복잡도의 문제로 다른 풀이도 진행해보았습니다.
풀이 (2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | const twoSum = (nums, target) => { let i = 0; let j = nums.length - 1; while (i < j) { let sum = nums[i] + nums[j]; if (sum < target) { i++; sum = nums[i] + nums[j]; } else if (sum > target) { j--; sum = nums[i] + nums[j]; } else { return [i, j] } } } | cs |
이처럼 while 반복문 내에서 i, j를 설정하고 sum의 값이 target보다 크거나 작을 때의 각각 값을 변화해서 target 값을 찾아주도록 하였습니다.
다만, 여기서 작은 문제가 발생합니다. nums로 주어지는 배열이 정렬이 되어있다라는 가정 하에 해당 문제 풀이가 가능합니다. 저도 처음에는 별도의 조건이 명시되어 있지 않아서 넘어갔으나, 왠지 정렬이 되어있는 배열로 문제를 주신 것 같아서 돌려봤더니 문제가 해결되었습니다.
이러한 조건이 명시되어 있었다면, 더 좋았겠지만 시간 복잡도를 줄여서 더욱 신났던 코드카타였습니다.
🎬 Day2
문제
reverse 함수에 정수인 숫자를 인자로 받습니다. 그 숫자를 뒤집어서 return해주세요.
x: 숫자
return: 뒤집어진 숫자를 반환!
예를 들어,
x: 1234
return: 4321
x: -1234
return: -4321
x: 1230
return: 321해당 문제도 어려운 문제는 아닙니다. 많이 풀어봤던 문제로 머리 속에서 reverse, split, join 등의 함수가 생각나서 풀이하였습니다.
다만, 마이너스의 유무였습니다. 숫자가 0보다 작을 때는 위와 같은 방식으로 해버리면 마이너스가 맨 뒤로 가버리게 되는 참사가 발생합니다.
이를 해결하기 위해서 고민을 했지만, 결국 백엔드 동기들의 도움을 요청했습니다. 코드를 먼저 보고 오시죠.
1 2 3 4 5 6 7 8 | const reverse = x => { let reversedX = String(Math.abs(x)) if (x >= 0) { return Number(reversedX.split('').reverse().join('')) } else { return -Number(reversedX.split('').reverse().join('')) } } | cs |
저는 숫자를 단순히 문자로 바꾸고 나서 0보다 클 때의 조건처럼 문제를 풀이하였습니다. 그러나 이렇게 되면 위에서 언급한 문제가 발생하였습니다. 결국, 0보다 작을 때 마이너스를 없애줘야하는데 이에 대해서 고민을 했지만, 해결을 하지 못했습니다.
오히려, 배열로 나누어졌을 때 index[0]인 마이너스를 앞으로 보낼 순 없을까 고민했지만, 이 또한 너무 코드가 복잡해질 것 같아서 여러 방법을 생각해봤습니다. 그러나 최종적으로 저의 갓갓 사전 스터디 백엔드 조원들에게 SOS를 쳤고, 힌트를 통해 문제를 해결했습니다.
결국, 위와 같이 숫자에 Math.abs(x)로 절대값을 주면 간단하게 해결됩니다. 그렇다면, 마이너스는 사라지고 이후 0보다 작을 때는 나온 결과 숫자에 마이너스(-)만 앞에 붙여주면 되죠.
else {
return -Number(reversedX.split('').reverse().join(''))
}바로 이렇게 말입니다. 쉬운 문제들이었지만, 문제를 누군가에게 풀이를 해도록 도와주거나 또한 반대로 해결이 되지 않아 조언을 받으면서 스스로 습득해나가는 방식에 대해서 잘 배울 수 있는 세션이었던 것 같습니다.
코드카타는 6주간 계속될 계획이라 모든 문제를 업로드하기엔 힘들 것 같아서 추후에는 스스로 많이 깨닫게 해준 알고리즘에 대해 업로드하려 합니다.
다음 블로그 글도 기대 부탁드립니다🤓
