알고리즘(Python, JavaScript) - 콜라츠 추측

Input

1
2
3
input_one = 6
input_two = 16
input_three = 626331

Expected Output

1
2
3
output_one = 8
output_two = 4
output_three = -1

목표

  • 입력된 수가 짝수라면 2로 나눕니다.
  • 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
  • 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.
  • 최고 500번을 수행하며 그 안에 성공하면 수행 횟수를, 불가능하면 -1을 리턴한다.

조건

  • 1 <= 입력 <= 8,000,000
  • 최고 500번 수행

코드

Python3

1
2
3
4
5
6
7
def solution(num):
    answer = 0
    while num != 1 and answer <= 500:
        is_odd = num % 2
        num = (num*3)+1 if is_odd else num/2
        answer += 1
    return answer if num == 1 else -1

JavaScript

1
2
3
4
5
6
7
8
function solution(num) {
    var answer = 0;
    while(num !== 1 && answer <= 500){
        num = num%2 === 0 ? num/2 : num*3+1;
        answer++;
    }
    return (num === 1) ? answer : -1;
}

해설

  • 처음 코드로 진입하면 아직 입력값을 바꾸는 작업을 하지 않았기 때문에 수행 횟수는 0이다.
  • 처음부터 입력이 1이라면 while 루프로 진입이 불가능하고 바로 마지막 코드로 가게된다.
  • 입력 값이 1이면 0인 answer을 리턴한다.
  • while 루프로 진입하면 입력 값을 바꾸는 작업을 수행하고 입력 값이 1이 되지 않는다면 500회만 수행하고 그 전에 1이 되면 while 루프로 진입하지 않고 수행한 횟수를 answer에 기록하고 그것을 리턴한다.