https://school.programmers.co.kr/learn/courses/30/lessons/12980
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1) 풀이
이 문제도 며칠간을 끙끙대다가 겨우 풀었는데 생각해보면 좀 어이없다..
일단 나는 우선 이 문제를 자료형 Map 을 이용해서 key에 현재 있는 칸, value에 건전지 사용량을 저장했었다
Map 을 하나 만들어서 재귀함수를 이용해서 값을 넣어주고 그다음 값은 재귀로 또 보고 또 보고.. 이런 식으로 진행했으나
자바스크립트는 재귀의 깊이가 한정되어 있기 때문에 오류가 떴다
그래서 재귀함수를 사용하지 않기 위해, 재귀함수 내의 로직들을 밖으로 빼내고 Map에서 배열로, 즉 2차원 배열로 똑같이 저장하고 탐색해보려 했다! (Map 자료형의 특성상 index로 접근이 불가한데, 탐색하기가 너무 번거롭기 때문)
로직은 다음과 같다.
처음에 어차피 1만큼을 가야 점프든, 순간이동이든 할 수 있기 때문에 [1, 1] 를 기본적으로 집어넣어준다
그리고 그 배열에서 첫번째 요소를 shift()로 빼낸 다음, 이 요소에서 x2 하여 순간이동한 값과 건전지 사용량(현재는 첫번째 칸 기준이기 때문에 1), 그리고 +1 해서 +1된 건전지 사용량 모두를 배열에 넣어준다. 그리고 또 다시 다음 첫번째 요소를 shift() 해서 똑같은 과정을 진행하되, 특정 칸 값이 이미 배열에 존재하면 건전지 사용량을 비교하여 더 작은 값을 넣어주곤 했다. 그렇게 해서 만들어진 반복문 로직은 다음과 같다
while(gone.length!==0){ //gone은 값을 저장하는 2차원 배열 . 해당로직은 결과적으로 필요없다
cur=gone.shift();
if(cur[0]===n) return cur[1];
if(cur[0]>n) continue;
if(cur[0]*2===n) return cur[1];
if(cur[0]+1===n) return cur[1]+1;
tmp=gone.findIndex((e)=>e[0]===cur[0]*2);
if(tmp!==-1){
if(gone[tmp][1]>cur[1]) gone[tmp][1]=cur[1];
}else gone.push([cur[0]*2,cur[1]]);
tmp=gone.filter((e)=>e[0]<=cur[0]&&e[1]<=cur[1]);
if(tmp.length!==0) continue;
if(cur[0]*2!==cur[0]+1){
tmp=gone.findIndex((e)=>e[0]===cur[0]+1);
if(tmp!==-1){
if(gone[tmp][1]>cur[1]+1) gone[tmp][1]=cur[1]+1;
}else gone.push([cur[0]+1,cur[1]+1]);
}
}
해당 로직을 돌았더니 정답은 다 나오는데, 시간초과가 여전히 나왔다.
혹시 n이 너무 커서 오래 걸리나? 하는 생각에 n을 n%2가 0이 아닐 때까지 2로 나눠주는 반복문을 저 반복문 앞에 넣어줬다. 나의 생각은, 어차피 x2로 순간이동을 하고, n%2가 0이 아닌 순간에는 1칸 앞으로 가야하는 타이밍일텐데, 그때부터 내가 저 로직을 사용하면 되겠다는 생각이었지만.. 사실 그렇게 따지면 이것만 이용하면 저 로직 필요없이 정답을 구할 수 있다..! 이거를 이 새벽에서야.. 몇날 며칠 고민하다가 떠올리게 되었다.
혹시나 해서 다 지워봤더니.. 어처구니 없이 정답이었다
오늘도 삽질했지만.. 그래도 한 문제 맞혔으니까 😂
2) 최종 소스코드
function solution(n)
{
let count=0;
while(n!==0){
if(n%2!==0) count++;
n=Math.floor(n/2);
}
return count;
}
'Problem Solving > 프로그래머스' 카테고리의 다른 글
[프로그래머스/JavaScript] 멀리 뛰기 (2) | 2022.11.24 |
---|---|
[프로그래머스/JavaScript] [1차] 캐시 (0) | 2022.11.18 |
[프로그래머스/JavaScript] 카펫 (0) | 2022.11.16 |
[프로그래머스/JavaScript] H-Index (0) | 2022.11.13 |
[프로그래머스/JavaScript] 다음 큰 숫자 (0) | 2022.11.08 |