[Programmers #12943] - 콜라츠 추측

(Lv. 1) 콜라츠 추측 (문제 링크)

문제 설명

1937년 Collatz는 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다고 추측했다.

작업은 다음과 같다.

1. 입력된 수가 짝수면 2로 나눈다.
2. 입력된 수가 홀수면 3을 곱하고 1을 더한다.
3. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복한다.

예를 들어, 주어진 수가 6이라면, (6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1)이 되어 총 8번 만에 1이 된다.

위 작업을 몇 번이나 반복해야 하는지 return하는 solution 함수를 완성하라.

단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 -1을 return하라.

제한 조건

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

입출력 예시

---

접근 방식

1. 입력값은 숫자, 출력값은 일련의 작업과정을 반복한 횟수다.
2. 목표는 일련의 작업과정을 거쳐서 입력값을 1로 만드는 것이고, 작업의 제한 횟수는 500회다.
3. 따라서, 작업이 500회 반복할때까지 입력값이 1이 나오는지 반복해서 체크하고, 나오지 않는 경우 -1을 return하도록 한다.
4. 입력값이 1인 경우, 즉시 반복문을 빠져나오고 기본값인 0을 return한다.
5. 입력값이 짝수인지 홀수인지 구분하여 각각 연산을 수행한다.
6. 연산을 수행했다면 작업횟수를 1회씩 추가한다.
7. 최종 결과를 출력한다.

코드

function solution(num) {
  let answer = 0; // 반복 횟수

  // 500회 반복
  while (answer < 500) {
    // 입력값이 1인 경우
    if (num === 1) break;
    // 홀수/짝수에 따른 연산 수행
    else num % 2 === 0 ? (num /= 2) : (num = num * 3 + 1);
    // 작업 횟수++
    answer++;
  }
  // 작업을 500회 넘게 돌았는데도 입력값이 1이 안됨 -> -1 출력
  if (num !== 1) answer = -1;

  // 결과 출력
  return answer;
}

---

주요 개념

• 반복의 주체(기준), 방법을 생각하자.