[Programmers/JAVA] 콜라츠 추측 / 프로그래머스 코딩 테스트 연습

콜라츠 추측

---

문제 설명

 

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

 

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

---

예시

num	return
6	8
16	4
626331	-1

 

---

코드 해석 및 전체 코드

 

알고리즘

1. 반환값 변수 선언

2. long 타입 변수 n을 num으로 초기화 선언

3. 반환값이 500일때까지 반복

4. n이 1일 때 answer 반환

5. n이 짝수인지 홀수인지 판단하여 계산

6. answer++

7. while문에서 반환 못할 시 while문 종료 후 -1 반환

 

부연 설명이 필요한 단계만 작성

2. long 타입 변수 n을 num으로 초기화 선언

: 큰 수일 경우 홀수 계산식 때 int형 범위 초과하므로 long 타입으로 선언

예시 수 626331은 500번을 계산해도 1이 되지 않는다. 하지만 int형으로 변수를 선언할 시 홀수일 때 계산 시 num * 3 +1을 하면서 int형 범위를 초과하게 되므로 int형보다 더 큰 타입으로 선언해주어야한다.

 

3. 반환값이 500일때까지 반복

문제 조건 중 500번 초과 시 -1을 반환하라는 조건에 의해 500일 때까지 반복한다.

 

4. n이 1일 때 answer 반환

while문 탈출 후 answer를 반환하려고 했지만 answer가 500 초과인지 확인 후 answe값 또는 -1을 반환해야하므로 while문 탈출 대신 answer 반환으로 작성하였다. 

 

5. n이 짝수인지 홀수인지 판단하여 계산

n이 짝수일 경우에는 n을 2로 나누고, 홀수일 경우에는 n을 3으로 곱한 뒤 1을 더한다. 

 

7. while문에서 반환 못할 시 while문 종료 후 -1 반환

while문에서는 1이 될 경우 answer를 반환한다. 하지만 while문이 종료되었음에도 반환되지 못했다면 -1을 반환한다.

 

class Solution {
    public int solution(int num) {
        int answer = 0;
        long n = num;
        
        while(answer <= 500){
 
            if(n == 1) return answer;

            n = n % 2 == 0 ? n / 2 : n * 3 + 1;
            answer++;
        }
        
        return -1;
        
    }
}

---

github

programmers