[프로그래머스] - 콜라츠 추측(C#)

콜라츠 추측

오늘은 "콜라츠 추측" 문제에 대해서 살펴보겠습니다. 이번에도 하샤드 수 처럼 문제의 이름이 상당히 어렵게 느껴집니다. 문제 설명을 한번 보도록 하겠습니다.

 

문제 설명

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을 완성해 주세요. 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.

 

제한 사항

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

 

입출력 예

n	result
6	8
16	4
626331	-1

 

입출력 예 설명

입출력 예 #1
문제의 설명과 같습니다.

입출력 예 #2
16 → 8 → 4 → 2 → 1 이 되어 총 4번 만에 1이 됩니다.

입출력 예 #3
626331은 500번을 시도해도 1이 되지 못하므로 -1을 리턴해야 합니다.

 

시작 코드

public class Solution {
    public int solution(int num) {
        int answer = 0;
        return answer;
    }
}

 

나의 풀이

public class Solution {
    public int solution(int num) {
        int cnt = 0;
        long n = num;
        while(n != 1)
        {
            ++cnt;
            n = n % 2 == 0 ? n / 2 : n * 3 + 1;
        }
        if(cnt > 500) { cnt = -1; }
        return cnt;
    }
}

코드풀이를 먼저 살펴보겠습니다. int형 num을 입력받으면서 시작됩니다. int와 long 타입으로 각각 cnt와 n을 선언해주고, long타입으로 사용해 주기 위해 n에 num을 넣어줍니다. while문을 통해 n이 1이 아닌동안 cnt를 더하고, 삼항연산자 계산식을 실행시킵니다. 식을 살펴보면 n을 2로 나눈 나머지가 0일때는 n/2를 n에 넣어주고, 아니라면 n*3 + 1을 n에 넣어줍니다. while문에서 빠져나와 다음 if문에서 cnt가 500보다 크다면 cnt를 -1로 만들어 리턴해줍니다.

 

이번에도 새로운 기술이 등장한 것은 아닙니다. 정말 단순하게 문제에서 제시한 조건들에 모든 부분이 충족되도록 직관적으로 문제를 풀었습니다. 주어진 수가 1이 될 때까지 계산과정을 거쳐야 하기 때문에 while문을 작성하였고, 횟수를 나타내는 cnt를 통해 몇번 반복했는지 세어줍니다. 그리고 문제에 제시된 계산식을 삼항연산자로 축약하여 표현했습니다. 시도횟수가 500을 넘으면 -1을 반환해야한다고 문제에서 이야기 했기 때문에 while문 다음에 if문이 작성되었습니다.

 

<NEXT>

오늘은 "콜라츠 추측" 문제를 풀어보았습니다. 어려워 보이는 이름이지만, 문제를 살펴보면 주어진 조건에 맞춰 작성해주면 크게 어려울 것은 없었습니다. 다음에는 "서울에서 김서방 찾기" 문제를 살펴보도록 하겠습니다. 감사합니다.