Javascript 콜라츠 추측

Javascript 콜라츠 추측

 

 

문제 :

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다. 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

예를 들어, 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.

 

제한사항

• 입력된 수, num은 1 이상 8000000 미만인 정수입니다.

입출력 예

n  / result

6	8
16	4
626331	-1

주어진 코드  ↓

function solution(num) {
    var answer = 0;
    return answer;
}

---

일단 필요한 로직이 3가지 정도가 보인다.

첫번째는 짝수 홀수를 구분하여 연산하는 것이 필요하고,

두번째는 누적된 값을 반복해서 연산하는 것이 필요하다. 이 부분을 재귀로 풀어볼 수 있을 것 같다.

세번째는 500번 반복했을 때 -1을 반환하는 것이다.

 

function solution(num) {
    let count = 0;
    
    function isEven(num){
        if(num % 2 === 0){
            num = num / 2;
        }else{
            num = (num * 3) + 1;
        }
        count++;
        // 짝홀수 여부에 따른 연산과 카운트 증가
        
        if(num === 1){
            return count;
        }else if(count === 500){
            return -1;
        }else{
            return isEven(num);
        }
        // 재귀 탈출 구문과 500번 카운트 예외 분기
        // 아닌 경우 계속해서 재귀 호출
    }
    return isEven(num);   
    // 재귀함수 최초 실행
}

재귀함수는 탈출 구문을 잘 작성하지 않으면 무한 루프에 갇히게 된다.

이렇게 풀었더니 테스트 케이스에서는 통과되었지만,

제출하려고 보니 테스트13번에서 실패가 뜬다.

이유는 최초 주어진 수가 1인 경우에 대해 처리하지 못하는 문제가 있었다.

그래서 최초 주어진 수 1에 대한 예외 처리를 해보았다.

 

function solution(num) {
    let count = 0;

    function isEven(num){

        if(count === 0 && num === 1){
            return 0;
        }

        if(num % 2 === 0){
            num = num / 2;
        }else{
            num = (num * 3) + 1;
        }
        count++;

        if(num === 1){
            return count;
        }else if(count === 500){
            return -1;
        }else{
            return isEven(num);
        }
    }
    return isEven(num);
}

아무것도 하지 않았을 때 (count가 0일 때)

0을 리턴하도록 하여 모든 테스트 케이스를 통과할 수 있었다.

 

여기까지가 나의 풀이 방법이었고,

다른 풀이법도 찾아보았다.

 

function collatz(num) {
    var answer = 0;
    while(num !=1 && answer !=500){
        num%2==0 ? num = num/2 : num = num*3 +1;
    answer++;
  }
    return num == 1 ? answer : -1;
}

while 문에서 1이 아니면서 카운트가 500이 아니면 반복해서 계산하도록 하였다.

반복문에서 삼항연산자를 통해서 지속적으로 num에 계산 값을 할당하는 방식이다.

while문이 반복되면서 카운트도 진행한다.

연산을 반복하는 부분을 재귀로 구현하는가

아니면 while문에서 연산으로 반복하여 구현하는가

이 두가지 선택지가 있다는 것을 기억하자!

 

Javascript 콜라츠 추측