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

1. 문제이해

https://programmers.co.kr/learn/courses/30/lessons/12943

코딩테스트 연습 - 콜라츠 추측

 

콜라츠의 추측을 통해 주어진 정수를 몇번의 과정을 통해 1로 만들수 있는지를 출력하는 것이 목표이다.

콜라츠의 추측 과정은 다음과 같다.

 

1-1. 입력된 수가 짝수라면 2로 나눕니다.

1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.

2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

 

 

 

2. 문제풀이

 

위와 같은 콜라츠의 추측 방식을 그대로 코드로 구현해주면 된다.

while문을 통해 num이 1이 아닌 경우 계속 반복하도록 하고,

while문 안에 if문을 통해 위의 내용을 구현해주었다.

 

단, 문제에서 언급했듯, 횟수가 500번을 넘어가면 -1을 출력하도록 해야 하는 것이 관건이다.

예를 들어, 위의 예제의 626331 같은 경우,

단순히 구현한 뒤 다음 숫자를 집어넣게 되면, 다음과 같은 결과가 나온다.

(소스코드의 1번 경우)

 

 

분명 횟수는 500번이 넘어가는데, 결괏값은 488이 나와 에러가 뜨게 된다.

이유는 바로 int형을 사용했기 때문이다.

int형을 그대로 사용할 시, 중간 계산값이 int형이 지원하는 범위를 넘어버리기 때문에,

올바른 결과가 나오지 않게 된다.

따라서, int형으로 입력받은 num값을, long long 형으로 다시 저장해주어 계산해야 한다.

 

주어진 틀은 다음과 같았다.

 

 

 

3. 소스코드

 

1. long long 형을 사용하지 않고 단순 구현한 경우 (실패)

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
    int answer = 0;
    
    while (num != 1){
        if(answer == 500){ // 작업을 500번 반복한 경우
            answer = -1;
            break;
        }
    
        else{ // 작업횟수가 500번 미만인 경우
            if(num % 2 == 0){ // 짝수인 경우
                num = num / 2;
                answer++;
            }
            else { // 홀수인 경우
                num = (num * 3) + 1;
                answer++;
            }
        }
    }
    return answer;
}

위에서 언급했듯, long long 형을 이용하지 않고 위와 같이 코드를 짜게 되면

int 형의 범위를 넘어서는 값이 주어지는 경우, 올바른 값이 나오지 않게 된다.

따라서, 밑의 소스코드처럼 한번 가공을 해주어야한다.

 

 

 

2. long long 형을 이용한 경우 (성공)

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
    int answer = 0;
    long long number = num; // num을 long long 타입으로 변경
    
    while (number != 1){
        if(answer == 500){ // 작업을 500번 반복한 경우
            answer = -1;
            break;
        }
    
        else{ // 작업횟수가 500번 미만인 경우
            if(number % 2 == 0){ // 짝수인 경우
                number = number / 2;
                answer++;
            }
            else { // 홀수인 경우
                number = (number * 3) + 1;
                answer++;
            }
        }
    }
    return answer;
}

위 실패한 코드에서 long long number = num;을 추가해 준 뒤,

밑의 while 문 안의 num을 모두 number(long long형 변수)로 바꿔주었다.

long long 형으로 모두 바꾸어 계산했더니 더이상 범위를 넘어서지 않아

올바른 결괏값이 출력되었다.😊

 

 

---

오늘로만 벌써 4번째 포스팅이다..😏

그동안 여러 시험에 번아웃이 심하게 와서 코딩공부에 약간 소홀했던것 같아

오늘은 좀 많은 문제를 풀어보려고 하는 중이다.

(그래봤자 쉬운 문제 위주긴하지만..😂 푸는 것에 의의를 두기로 했다..ㅎㅎ)