[프로그래머스] 콜라츠 추측

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

 

 

 

 

 

** Javascript

 

 

1) 내 첫번째 풀이는 이렇다

 

function solution(n) {
    let number = n;
    let answer = 0;
    while (number !== 1) {
        if (number % 2) {
            number = number * 3 + 1;
        } else {
            number /= 2;
        }
        answer++;
        if (answer === 500) {
            return -1;
        }
    }

    return answer;
}

 

 

2) 코드를 간결하게 줄여보았다.

 

function solution(n) {
    let answer = 0;
    while(n > 1) {
        n =  (n % 2) ? n * 3 + 1 : n / 2;
        answer++;
    }
    return answer >= 500 ? -1 : answer;
}

 

 

while 문 안에서 계속 반복될 수도 있으니 다시 수정해주었다.

 

function solution(n) {
    let answer = 0;
    while(n > 1) {
        n =  (n % 2) ? n * 3 + 1 : n / 2;
        answer++;
        if (answer >= 500) return -1;
    }
    return answer;
}

 

 

 

 

다른 풀이 중 추천을 가장 많이 받은 풀이는 재귀함수 달인의 풀이다.

 

// 문제가 개편되었습니다. 이로 인해 함수 구성이나 테스트케이스가 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
// 새로운 함수 구성을 적용하려면 [코드 초기화] 버튼을 누르세요. 단, [코드 초기화] 버튼을 누르면 작성 중인 코드는 사라집니다.
function collatz(num,count = 0) {
    return num == 1 ? (count >= 500 ? -1 : count) : collatz(num % 2 == 0 ? num / 2 : num * 3 + 1,++count);
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log( collatz(6) );

 

 

 

 

 

** Java

 

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

 

 

프로그래머스에서 input 값으로 public int solution(int num) 으로 주어지는데 그대로 하면 입력값이 626331일 때 통과되지 않는다.

혹시나 해서 long num 바꿨더니 바로 통과...

 

 

추천을 가장 많이 받은 풀이는 while 문 대신 for 문을 사용하였다. 500 번 반복문이 끝나면 무조건 -1을 리턴하도록

 

// 문제가 개편되었습니다. 이로 인해 함수 구성이나 테스트케이스가 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
// 새로운 함수 구성을 적용하려면 [코드 초기화] 버튼을 누르세요. 단, [코드 초기화] 버튼을 누르면 작성 중인 코드는 사라집니다.
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));
    }
}

 

 

 

** Python

 

이번 풀이는 바꿀 게 많이 없어서 python으로도 해봤다.

 

def solution(num):
    answer = 0
    while num > 1:
        num = num / 2 if num % 2 == 0 else 3 * num + 1
        answer += 1
        if answer >= 500: return -1
    return answer

 

 

 

 

다른 사람들이 푼 풀이 중 추천을 가장 많이 받은 풀이이자 억지라고 욕을 받은 풀이인데

맨 위에 참고로 가져온 java 풀이와 다를 바가 많이 없는데 욕 먹고 있다.

 

# 문제가 개편되었습니다. 이로 인해 함수 구성이나 테스트케이스가 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
# 새로운 함수 구성을 적용하려면 [코드 초기화] 버튼을 누르세요. 단, [코드 초기화] 버튼을 누르면 작성 중인 코드는 사라집니다.
def collatz(num):
    for i in range(500):
        num = num / 2 if num % 2 == 0 else num*3 + 1
        if num == 1:
            return i + 1
    return -1

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(collatz(6))

 

 

 

 

 

위키피디아를 보니 콜라츠 추측은 3n + 1 추측, 울람 추측, 헤일스톤(우박) 수열 등의 다른 이름을 갖고 있다고 한다.

 

 

설명 중에 이게 제일 골때린다.

 

이 추측은 컴퓨터로 268[1] 까지 모두 성립함이 확인되었다. 그러나, 아직 모든 자연수에 대한 증명은 발견되지 않고 있다. 이 문제의 해결에 500달러의 현상금을 걸었던 에르되시 팔은 "수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다."는 말을 남겼다.

다음과 같은 통계적인 설명을 생각하면 이 추측은 참일 가능성이 높아 보인다. 그러나 이것이 콜라츠 추측을 증명하는 것은 아니다.

이 조작에 의해 만들어지는 홀수들만 생각하면, 다음에 오는 홀수는 평균적으로 그 전의 수의 3/4정도의 값을 갖는다. 따라서 홀수의 수열은 점점 작아져 결국 1이 될 것이다.

 

https://ko.wikipedia.org/wiki/%EC%BD%9C%EB%9D%BC%EC%B8%A0_%EC%B6%94%EC%B8%A1

콜라츠 추측 - 위키백과, 우리 모두의 백과사전

 

 

 

이런 기사도 있다.

 

https://www.yna.co.kr/view/RPR20210712006100353

[AsiaNet] Bakuage, '콜라츠 추측' 증명한 사람에게 상금 1.2억 엔 지급 | 연합뉴스