매일 매일 하루 한 문제씩.
꾸준히 이어가는 코딩테스트 풀이 기록 ✅
오늘 푼 코딩테스트 문제는 '최대공약수와 최소공배수'
최대공약수와 최소공배수를 손으로 풀어서 구하는 건 그리 어렵지 않다.
하지만 이 문제, 또는 공약수/공배수와 관련된 문제는 여러번 풀어보아도 체감 난이도가 높은게 사실이다.
이유가 뭘까 좀 고민해봤는데...
계속 마음에 걸리는게 '유클리드 호제법'이다. ㅎㅎ. . .
사실 오늘 푼 문제는 2개의 숫자가 주어지고 그 수에 대한 최대공약수와 최소공배수를 구하는 것이기에 그리 어렵지 않은 문제가 될 것이다.
하지만 프로그래머스 유사 문제 중에 N개의 최소공배수라는 문제가 있는데 이건 진짜 몇번을 풀어도 새롭고 새롭다 ㅎㅎㅎ
계속 풀다보면 저 문제를 분명 다시 맞닥뜨리게 될 것인데... 지금 다시 푼다 해도 아마 제대로 풀지 못하고 또 어버버 할 것 같다.
오늘 코딩테스트 TIL을 작성한 후에 유클리드 호제법에 대해 각잡고 정리해야겠다.. ㅠㅠ
유독 취약한 부분이 알고리즘, 그리고 컴퓨터공학과 연관된 내용인 것 같은데 비전공자라는 특성때문에 어쩔 수 없다고 생각되는 부분이지만 한편으론 요 포인트를 빠르게 극복해내야 코딩테스트에 대한 체감 난이도도 단시간에 줄일 수 있을 것 같다.
반복해서 외우고 익혀야지..!
오늘 문제를 풀면서 새롭게 깨달은 점은, 자바스크립트에서 immutable한 방식으로 문제를 풀려면 때로는 수학 관련 공식이나 정의를 아는게 좋다는 점이었다.
자바는 아래 풀이를 보다시피 for문, while문을 사용해서 풀었는데, 자바스크립트는 근 20분을 고민했는데도 이외의 방법이 떠오르질 않았다.
결국 시간이 너무 지체되어 다른 풀이를 참고했는데, 최소공배수를 구하는 아주 간단한 공식(두 수를 곱하고 최대공약수로 나눈 값)을 확인하고 나니 약간 허무한 기분도 들었다.
결국 간단한 공식을 제대로 추출해내지 못해 허비한 시간...
이후에도 비슷한 문제가 나오면 꼭. 다시 상기해서 풀어야지.
그래도 재귀 방법으로 최대공약수를 구해본 것은 나름 의미있는 성과.. :)
문제.
java solution
자바로 푼 코드.
최대공약수와 최소공배수를 구하는 메서드를 각각 getGcd, getLcm로 분리하여 구해봤다.
주어진 두 수의 크고 작음을 판별하여 문제 풀 때 좀 더 편하려고(ㅎㅎ) smallNumber라는 변수를 선언했는데.
자바스크립트에서는 Math.max() 메서드를 활용해 별도의 변수 할당 없이 판별.
역시 한 문제를 가지고 두 개의 언어로 풀다보면 처음에 풀 땐 생각지 못한 부분들을 두 번째 풀면서 새롭게 떠올리기도 한다.
최대공약수는 두 수 중 작은 수를 시작으로 1씩 줄여가면서 for문을 활용해 구했고.
최소공배수는 accumulator라는 변수를 선언해서 while문 안에서 조건에 부합할 때까지 반복적으로 나눠나갔다.
class Solution {
public int[] solution(int n, int m) {
int smallNumber = n;
if (smallNumber > m) {
smallNumber = m;
m = n;
}
int gcd = getGcd(smallNumber, m);
int lcm = getLcm(gcd, smallNumber, m);
return new int[]{gcd, lcm};
}
public int getGcd(int smallNumber, int m) {
for (int i = smallNumber; i > 0; i -= 1) {
if (smallNumber % i == 0 && m % i == 0) {
return i;
}
}
return 1;
}
public int getLcm(int gcd, int smallNumber, int m) {
if (m % smallNumber == 0) {
return m;
}
int accumulator = 1;
while (true) {
if (gcd > 1 && smallNumber % gcd == 0 && m % gcd == 0) {
accumulator *= gcd;
smallNumber /= gcd;
m /= gcd;
continue;
}
return accumulator * smallNumber * m;
}
}
}javascript solution
최대공약수를 구할 때, 재귀를 사용해보려고 했는데 다행히(?) 먹혀들어갔다.
divisor를 별도로 주지 않고 할 수 있는 방법을 계속 고민해봤는데... 적당한 솔루션이 떠오르지 않아 결국 3개의 인자가 getGcd() 메서드 안에 들어가게 되었다.
최소공배수 구하는 공식은... 보면 볼수록 아쉬운 점. 왜 빨리 캐치하지 못했을까... 사실 문제 풀기 전에 손으로 몇 개의 케이스를 써보고 풀었는데.
그 때 좀 더 신경썼더라면 알아챌 수 있는 공식.ㅠㅠ 놓치지 말자.
function getGcd(small, large, divisor) {
if (large % divisor === 0 && small % divisor === 0) {
return divisor;
}
return getGcd(small, large, divisor - 1);
}
function getLcm(small, large, gcd) {
return (small * large) / gcd;
}
function solution(n, m) {
const small = Math.min(n, m);
const large = Math.max(n, m);
const divisor = small;
const gcd = getGcd(small, large, divisor);
const lcm = getLcm(small, large, gcd);
return [gcd, lcm];
}홀맨님이 추천해주신 자바스크립트 문제모음집이 있던데 가격이 좀 나가지만 새해 기념으로 하나 사야겠다.
아직 읽지 않은 책들은 많지만 마음에 계속 부채의식을 느껴야 좀 읽을것 같아서 ㅎㅎㅎ
자꾸 문제 풀고 코딩을 하면서 새롭게 알아가는 부분들은 정리하고..
어제 코테 한번 봐 보니 공부할 게 새삼 많다는 점 다시한번 깨닫는다.
할 건 많고! 시간은 부족하고! 하지만 언제나 그랬으니 오늘 하루도 더욱 효율적으로 성장하며 살아가자.
