Lv1. 콜라츠 추측 [O]

문제 출처: programmers.co.kr/learn/courses/30/lessons/12943

코딩테스트 연습 - 콜라츠 추측

1. 문제 이해

입력된 수가 짝수라면 2로 나눔
홀수라면 *3 + 1
주어진 수가 1이될때까지 반복
다음작업이 반복되는 횟수 리턴
500번 반복해도 안되면 -1출력
num은 8백만 이하

2. 풀이 계획

반복문 or 재귀
재귀면 전역변수 쓰거나 cnt인자 넘겨줘야함
반복문이 재실행되거나 재귀 호출때마다 cnt += 1
cnt > 500이면 -1출력
그전에 num이 1이되면 반복문나와서 cnt 출력

3. 구현

# 반복문으로 푼 풀이

def solution(num):
    cnt = 0
    while True:
        if cnt > 500 :
            return -1
        if num == 1:
            return cnt
        if num % 2 :
            num = num * 3 + 1
        else :
            num //= 2
        cnt += 1

# 재귀로 푼 풀이

cnt = 0
def solution(num) :
    global cnt
    cnt += 1
    if cnt > 500 :
        return -1
    if num == 1 :
        return cnt - 1 # 주의 : 맨처음에 1을 더해주므로 마지막에 1을 뺀값을 return해야함
    
    if num % 2:
        return solution(num * 3 + 1)
    else :
        return solution(num // 2)

4. 검토 및 개선