[프로그래머스] Lv.1 콜라츠 추측 - Java

🔥개인 취미 목적으로 프로그래머스 문제를 정리한 게시글입니다.

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

프로그래머스

✏️문제설명

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

1. 입력된 수가 짝수라면 2로 나눕니다.
2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
3. 결과로 나온 수에 같은 작업을 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

---

💻 소스 코드

class Solution {
    public int solution(int num) {
        long n = num;
        int count = 0;

        while (n != 1) {
            if (n % 2 == 0) {
                n = n / 2;
            } else {
                n = n * 3 + 1;
            }
            count++;

            if(count > 500) {
                return -1;
            }
        }
        
        return count;
    }
}

위 코드는 주어진 정수 num에 대해 다음과 같은 작업을 반복하여 수행하고, 작업을 수행하는 데 필요한 반복 횟수를 반환하는 메서드를 구현한 것입니다.

코드의 작동 방식은 다음과 같습니다.

1. sum이라는 double형 변수를 선언하고 0으로 초기화합니다.
2. 주어진 배열 arr을 반복하며 모든 요소를 sum 변수에 더해줍니다.
3. 배열의 모든 요소를 더한 후, 배열의 길이로 나누어 평균을 계산하여 반환해 줍니다.

시간 복잡도

위 코드의 시간 복잡도는 배열의 길이에 선형적으로 비례합니다. 배열의 모든 요소를 한 번씩 더하기 때문에 시간 복잡도는 O(n)입니다. 여기서 n은 배열의 길이를 나타냅니다.

공간복잡도

위 코드의 공간 복잡도는 입력 배열의 길이와 관계가 없고, 상수 공간을 사용합니다. 따라서 공간 복잡도는 O(1)입니다.

메서드 내에서 추가적인 데이터 구조나 배열을 생성하지 않고 고정된 수의 변수만 사용하므로 메모리 사용량이 상수로 유지됩니다.