[프로그래머스] 콜라츠 추측 (12943)

목차

1. 문제 링크
2. 문제 설명
3. 제한 사항
4. 풀이 [ C ]
5. 풀이 [ Python3 ]

 

1. 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12943

 

2. 문제 설명

입력된 수가 짝수라면 2로 나누고, 홀수라면 3을 곱하고 1을 더합니다.

결과가 1이 될 때 까지 필요한 작업의 횟수를 반환하는 함수 solution을 완성하시오

단, 이미 결과가 1이라면 0을, 500번 반복할 때까지 1이 되지 않는다면 -1을 반환할 것

 

3. 제한 사항

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

 

4. 풀이 [ C ]

 

풀이 아이디어
1. C에서 int 최댓값은  2,147,483,647입니다, 범위를 벗어날 수 있으므로 long long int에 저장하도록 합시다.

2. for문을 이용해, 지정된 시행 횟수인 500번을 돌리도록 합시다. 벗어나면 바로 -1을 return해줍시다.

3. 삼항연산자를 이용해서 쉽게 연산할 수 있습니다.

코드 (C)

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int num) {
    long long int answer = num;
    for(int i = 0 ; i < 500 ; i++) {
        if(answer == 1) return i;
        answer = (answer%2==0 ? answer/2 : answer*3+1);
    }
    return -1;
}

풀이 설명
1. long long int에 num을 저장합시다.

2. for문을 통해 500번 돌립니다. 이것이 시행 횟수입니다.

3. 만약 1이 된다면 해당 시점의 시행 횟수를 반환합니다.

4. 1이 아니라면, 삼항연산을 통해 시행을 추가합니다.

시간 복잡도
O(1)

5. 풀이 [ Python3 ]

풀이 아이디어

1. 시행 횟수를 저장할 변수 count를 만듭시다.

2. while문을 이용해 입력값 num이 1이 아닌 동안 반복합시다.

3. 짝수, 홀수를 구분하여 시행합시다.

4. 500번을 넘어간다면, 바로 -1을 리턴합시다.

코드 (Python)

def solution(num):
    count = 0
    while num != 1 :
        if num%2==0 :
            num = num/2
        else :
            num = num*3+1
        count += 1
        if 500 < count :
            return -1
    return count

풀이 설명
1. num값이 1이 아닌 동안 while문을 이용해 반복합니다.

2. 짝수일 때는 2로 나누고, 홀수일 때는 3을 곱하고 1을 더합니다.

3. 만약 500을 넘어간다면 바로 -1을 리턴합니다.

시간 복잡도

O(1)