[Java] 자바 알고리즘 / 프로그래머스 콜라츠 추측

문제 설명

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을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.

 

제한 사항

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

 

입출력 예

n     result

6       8

16       4

626331    -1

 

입출력 예 설명

입출력 예 #1

문제의 설명과 같습니다.

 

입출력 예 #2

16 -> 8 -> 4 -> 2 -> 1 이되어 총 4번만에 1이 됩니다.

 

입출력 예 #3

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

class Test {
    int answer = 0;
  public int test(int num) {
      if(num == 1){
            return answer;
        }
        if(answer==500){
            return -1;
        }
        answer++;
        if (num % 2 == 1) {
            // 홀수
            return solution(num * 3 + 1);
        } else{
            // 짝수
            return solution(num / 2);
        } 
  }
}

dev 흑구 Ver.

-해설

재귀메소드를 이용한 방식. 매개변수 num이 1인 경우는 바로 answer(연산횟수)로 반환됨. 혹은 여러번 처리된 후의 answer가 반환 됨. 두번째 조건문으로는 연산횟수가 500회인 시점을 판별하기 위해(>=을 쓰던 ==을 쓰던 상관없는 것이 한번에 +2로 증가하지 않게 설계하였기 때문 어차피 500에서 걸림) 조건을 걸고 참이면 -1을 리턴하도록 함. 홀수인 경우와 짝수인 경우를 나눗셈 연산으로 구별하여 다시한번 solution함수에 1이 아닌 매개변수 값을 각각의 짝 홀 조건에 따라 대입해주면 됨. 포인트는 answer를 클래스 변수로 뺐던 점(?)

 

class Collatz {
    public int collatz(int num) {
    long n = (long)num;
    for(int i =0; i<500; i++){      
      if(n==1) return i;
      n = (n%2==0) ? n/2 : n*3+1;            
    }
    return -1;
  }
    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        Collatz c = new Collatz();
        int ex = 6;
        System.out.println(c.collatz(ex));
    }
}

Others Ver.

-해설

for문의 횟수를 500으로 한정하고 각각의 경우에 따라 잘 return 되도록  설계함. 횟수가 500일때 return -1 하는 조건문이 사라진 점(왜냐하면 for문을 500번 하면 -1을 자동으로 리턴하도록 설계함.) 삼항연산자로 쉽게 짝수 홀수를 구분하여 값을 처리한다는 점. int의 숫자범위를 초과할 경우를 대비해 long으로 형변환하여 처리한점.

 

출처-https://sas-study.tistory.com