[알고리즘] 콜라츠 추측

구글링 구글링!!!!! 좀 해라 오류난 부분 구글링하면 나온다.

조급해하지 말고 차근차근 풀자...

항해99_알고리즘 주차 문제와 해결_27

[JAVA]

문제 참고 : https://programmers.co.kr/learn/courses/30/lessons/12943

문제 : [콜라츠 추측]

문제 설명

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을 리턴해야합니다.

---

내가 해 본 거

1. 문제 분석

1. 입력된 수가 짝수라면 2로 나누기
2. 입력된 수가 홀수라면 3을 곱하고 1을 더하기

- 주어진 수로 2개의 과정을 계산하고 결과가 1이 될 때까지 반복

- 이 작업을 몇 번 반복해야 하는지 반환하는 함수, solution 완성하기

- 작업을 500번해도 1이 안 되면 -1반환

 

2. 규칙 찾기

- 짝수 일 때 (num%2 == 0)

num = num/2

- 홀수 일 때 (num%2 == 1)

num = num*3+1

- 연산을 한 번 할 때마다 i+1 : 계산 몇번 했는지 계산

 

첫번째. i가 500번 될 때까지 while문 써보자.

두번째. while문 끝날 때까지 break 안되면 answer =-1

세번째. if 입력된 수가 짝수라면 num=num/2

네번째. else 입력된 수가 홀수라면 num=num*3+1

다섯번째. if num이 1과 같다면 answer = i번 했다는 거 넣어주고 break

여섯번째. break로 while문을 빠져나가지 못했다면 i++ 해주기

 

- i가 1부터 시작 해야함 (주어진 수 n이 6일 때)

n	i	num%2	num/2	num*3+1
6	1	짝수	6/2=3
	2	홀수		3*3+1=10
	3	짝수	10/2=5
	...
	7	짝수	4/2=2
	8	짝수	2/2=1

 

3. 코딩화

while(){

    answer =-1

    if (num%2==0){

       num = num/2

    } else {

       num = num*3+1

    }

    

    if (num==1) {

        answer = i

        break

     }

     i++ 

}

 

4. 구현

- 왜 또 뭐 왜 프로그래머스 코드 실행 다 되고 제출 한 거 채점도 되면서 꼭 한개가 실패하냐 ㅠㅠ

-> 왜 이것만 에러나나 봤더니 입력값은 1이고 리턴은 0이여야 하는군요. (해결)

- 500번 반복되는데 -1 반환 안되는 거도 찾았는데 num 타입이 int라서 범위를 벗어나서 결과가 안 나왔다. num을 long타입으로 바꿈 (큰 값을 계산하면 범위를 넘어서서 오버플로우 생김)

 

<Solution 클래스에 solution 메소드>

- 중간중간 잘 되는 지 테스트하려고 출력문 넣음

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

        int i=1;
        while (i<500){
            answer = -1;
            if(num%2==0){
                num = num/2;       //num = num/2
                System.out.println("i= "+i+" 짝수 계산= "+num);
            } else {
                num = num*3+1;  //num = num*3+1
                System.out.println("i= "+i+" 홀수 계산= "+num);
            }
            if(num ==1){
                answer = i;
                break;
            }
            i++;
        }
//        System.out.println("answer= "+answer);

        return answer;
    }
}

 

<팀원들과 스터디 후 해본거>

- while문 무한 반복 true를 써서 풀어보았다.

- 500 초과되는 num 구별은 while문에서 빼서 따로 쓰니깐 프로그래머스 통과 잘 된다!!

- 그리고 13번 테스트가 통과가 안 되었는데 알고보니 1을 입력 받으면 0으로 리턴해야해서 그랬던거다. 그래서 처음에 num이 1인거 바로 구별해줌!!

-> 다 통과된다!!

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

        //num이 1로 들어올 때 바로 리턴해준다.
        if(num==1){
            return answer;
        }

        int i=1;
        while (true){   //i<500 , 무한 반복 true를 써보자
            if(num%2==0){
                num = num/2;       //num = num/2
//                System.out.println("i= "+i+" 짝수 계산= "+num);
            } else {
                num = num*3+1;  //num = num*3+1
//                System.out.println("i= "+i+" 홀수 계산= "+num);
            }
            if(num ==1){
                answer = i;
                break;
            }
            i++;
        }
//        System.out.println("answer= "+answer);

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

        return answer;
    }
}

 

<전체 코드>

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

        int i=1;
        while (i<500){
            answer = -1;
            if(num%2==0){
                num = num/2;       //num = num/2
//                System.out.println("i= "+i+" 짝수 계산= "+num);
            } else {
                num = num*3+1;  //num = num*3+1
//                System.out.println("i= "+i+" 홀수 계산= "+num);
            }
            if(num ==1){
                answer = i;
                break;
            }
            i++;
        }
//        System.out.println("answer= "+answer);

        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        // write your code here
        Solution sol = new Solution();
        System.out.println(((sol.solution(6))));
        System.out.println(((sol.solution(16))));
        System.out.println(((sol.solution(626331))));
    }
}

 

<실행 결과>

8

4

-1

---

★ 다른분의 문제풀이

- 와 깔끔하다

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int num) 
{
   long long answer = num;

    for(int i=0; i<500; i++)
    {
        if (answer == 1)
            return i;

        answer = (answer % 2 == 0) ? (answer / 2) : (3 * answer + 1); 
    }

   return -1;
}

- 다들 잘하시네 ㅠ

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int num) {
    int a = num;
    int answer = 0;
    while (true)
    {
        if (answer >= 500) return -1;
        if (a == 1) return answer;
        a = a % 2 != 1 ? a / 2 : (a * 3) + 1;
        answer++;       
    }
}

-- 프로그래머스 코드실행 제출 후 채점 다 통과

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;
    }
}

--

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));
    }
}