[Java&알고리즘] 콜라츠 추측 (Level 1)

 

프로그래머스의 알고리즘 문제 및 풀이에 대해 차근차근 포스팅하려합니다.

 

저도 초보자이기도하고 알고리즘에 쉽게 다가갈 수 없는 부분들이 많기 때문에

최대한 알기 쉽게 정리해보려하고 알고리즘을 어려워하는 분들에게 도움이 되었으면 합니다.

 

많이 공유되고 토론이 될 수 있는 공간이 되었으면 좋겠습니다.

 

 

 

 

 

 

 

 

환경

언어 : 자바

단계 : 레벨 1단계 (입문자용)

정답률 : 85%

 

 

 

 

 

 

제목 

 

콜라츠 추측

 

 

 

 

 

 

문제 설명 및 코드

 

 

 

 

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 미만인 정수입니다.

 

 

 

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

 

 

 

 

 

입출력 예

 

 

n	return
6	8
16	4
626331	-1

 

 

 

 

 

 

 

 

반응형

 

 

 

 

 

 

 

 

문제 정답 코드

 

 

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

 

 

여기서 중요한 점은 int num 변수를 그대로 사용하면 

큰 숫자를 사용할 경우 오버 플로우가 발생된다는 점입니다.

 

그래서 long 변수를 별도로 만들어 num 값을 대입하였고

while를 통해서 1이 아닐 경우 계속 반복하면서

삼항 연산자를 통해 짝수와 홀수의 조건식을 달아주었습니다.

 

카운팅 변수인 answer가 500일 경우 -1 값을 반환하여 break를 통해 빠져 나와 주었습니다.

 

 

 

 

 

 

 

 

다른사람 풀이

 

 

 

class Solution {
    public int solution(long num) {
        int answer = 0;
 
        while(num != 1){
            answer++;
            if(answer==500)
                return -1;
            if(num%2==0){
                num/=2;
            }else{
                num=num*3+1;
            }
        }
        return answer;
    }
}

 

 

위와 똑같은 풀이식이지만 if esle 문을 활용한 코드입니다.

자기 취향에 맞게 풀이하시면 될 듯 합니다!