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

🔷 🖱️여기 클릭하면 문제로 이동해요!

이 글은 문제를 정리하고 저의 풀이를 보여드리는 거예요. 실제로 문제를 보고 풀어보세요. 클릭! 클릭! 해보세요! 🖱️

🔷 문제

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

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

위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요.
❗단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.
❗입력된 수, num은 1 이상 8,000,000 미만인 정수입니다.

✅ 입출력 예시

• 입력된 수가 6이라면 6 ➡️ 3 ➡️ 10 ➡️ 5 ➡️ 16 ➡️ 8 ➡️ 4 ➡️ 2 ➡️ 1 이 되어 총 8번 만에 1이 됩니다.

• 16 ➡️ 8 ➡️ 4 ➡️ 2 ➡️ 1 이되어 총 4번만에 1이 됩니다.

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

  
  
  
  

🔷 내가 만든 로직

✅ 실패한 로직

• while문으로 구현할 때
  • 1이 될 때 까지
  • 짝수일 때는 num /= 2 한 후, answer++
  • 홀수일 때는 num *= 3 + 1 한 후, answer++
  • 위의 연산을 끝낸 후, if num == 1이면 return answer
    
    
• for문으로 구현할 때
  • 500번 반복
  • 짝수일 때는 num /= 2 한 후, answer++
  • 홀수일 때는 num *= 3 + 1 한 후, answer++
  • 위의 연산을 끝낸 후, if num == 1이면 return answer

✅ 성공한 로직

• ❗num의 자료형은 long으로! int는 ❌
  • 모든 코드가 똑같은데도 불구하고 num의 자료형이 int이냐, long이냐에 따라 결과가 달라진다.
  • 그리고 num의 자료형이 long일 때의 결과만 통과한다.
    ➡️ 이유가 뭘까... 더 알아봐야겠다.
    
    
• while문으로 구현
  • 조건 : num이 1이 아닐 때
  • while(num != 1)
• while문 시작하자 마자 바로 루프 카운팅 시작
  • collatzCount++
• while루프가 500번 반복되면 바로 -1 반환
  • if문으로 구현
  • -1은 itsNotCollazNum변수명으로 의미부여
  • if(collazCount == 500) return itsNotCollazNum
• 짝수일 때는 num /= 2 , 홀수일 때는 num *= 3 + 1 한 후, num에 대입
  • 삼항연산자 이용
  • num = (num%2==0) ? (num/2) : (num*3+1)

🔷 실패한 나의 코드 1

public class CollatzConjecture {
    public static int solution(int num) {
        int answer = 0;

        while (num <= 1000) {
            if(num % 2 == 0) {
                num /= 2;
                answer++;
            }

            if (num == 1)
                return answer;

            if(num % 2 == 1) {
                num = (num * 3) + 1;
                answer++;
            }
        }

        answer = -1;
        return answer;
    }
}

⬇️ 결과는..🥲

🔷 실패한 이유

✅ 이상한 while문 조건

✅ if(num == 1)문 위치

🥲 바꿔서 다시 해봤지만 다시 실패함. 결국 예상한 실패 이유가 틀렸다는 뜻!

🔷 실패한 나의 코드 2

public class CollatzConjecture {
    public static int solution(int num) {
        int collatzCount = 0;
        int itsNotCollatzNum = -1;

        while (collatzCount <= 500) {
            if (num % 2 == 0) {
                num /= 2;
            } else  {
                num = (num * 3) + 1;
            }
            collatzCount++;

             if (num == 1) return collatzCount;
        }

        return itsNotCollatzNum;
    }
}

⬇️ 바꾼 점

✅ while()문 조건

while(num <= 1000) ➡️ while(collatzCount <= 500)

✅ if()문 * 3

if() if() if() ➡️ if() else if()

✅ if(num==1)문 위치

짝수연산과 홀수 연산 사이 ➡️ 짝수 연산과 홀수 연산 뒤에

✅ answer++문 위치

짝수 연산과 홀수 연산 각각에 ➡️ 짝수 연산과 홀수 연산에 모두 지우고, 짝수 연산과 홀수 연산이 끝나고 한번만 answer++할 수 있도록 했다.

⬇️ 결과는..🥲

아까보다 틀린 횟수는 확연하게 줄긴 했다..🥲

🔷 엄청나게 어이없는 실패한 이유2

✅ 새로 추가된 규칙

내가 처음 문제를 풀었을 때는 6월 3일!
그러나 6월 10일에
주어진 수가 1인 경우에는 0을 반환해 주세요.라는 제한 규칙이 추가되었다.
최근에 추가된 이 제한 규칙을 충족시키지 못했기 때문에 아무리 코드를 고쳐도 계속 똑같이 테스트5랑 테스트13번만 계속 틀리는 것이었다!

✅ num의 자료형

num의 자료형이 int일 때와 long일 때 return값이 달라진다.

num의 자료형이 int면 불합격, long면 통과된다.

🔷 드디어 성공한 나의 코드

class Solution {
    public int solution(long num) {
        int collatzCount = 0;
        int itsNotCollatzNum = -1;

        while (num != 1) {
            collatzCount++;

            if (collatzCount == 500)
                return itsNotCollatzNum;

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

        return collatzCount;
    }
}

⬇️ 바뀐점

✅ 결국은 다른 사람의 풀이를 참고하여 통과했다..

public static int sol(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;
}

✅❗ int num ➡️ long num

↳ 이유 : INT 오버플로우

num의 자료형이 int일 때와 long일 때 return값이 달라진다.

• public int solution(long num)
  ➡️ num=626331 일때 return -1
  ➡️ 통과
  
  

• public int solution(int num)
  ➡️ num=626331 일때 return 488
  ➡️ 불합격
  
  

✅ while문 조건

↳ while(collazCount <= 500) ➡️ while(num != 1)

문제의 조건은 num이 1일 떄는 0을 반환하고, num이 1이 될 때까지 콜라츠연산을 반복하는 것이므로 num이 1일 때는 루프를 타지 않아야 한다. 그러므로 while문의 조건이 collazCount <= 500이어야 하는 것이 아니라 num != 1인 것이 맞다.

✅ while문 안의 collatzCount++ 맨 위로 위치 변경

while문이 시작하자마자 카운팅을 시작해야지 collazCount가 500일 때 바로 -1을 반환시킬 수 있기 때문이다.

✅ while문 안의 if문 조건

↳ if(num ==1) return collazCount ➡️ if (collazCount == 500) return itsNotCollazNum

while문의 조건과 if문의 조건을 반대로 해놔서 이때까지 틀린 것이었다.
num이 1이면 while문이 돌아가면 안되고
collazCount가 500이 되면 while문이 멈춰야 되는 것이었는데
이것을 정반대로 해서
collazCount가 500이 될 때까지 num이 1이어도 while문이 돌아가게 했고 그래서 num이 1일 때 0을 반환해야 하는데, 콜라츠 연산 횟수인 collazCount를 반환되어 버렸다.

✅ return 값

↳ return itsNotCollazNum ➡️ return collazCount

이 문제는 콜라츠 연산의 횟수를 요구한 것이었는데
나는 -1을 반환했으니 당연히 틀리는 것이었다.

⬇️ 결과는..😄

🔷 solution함수의 매개변수num의 타입이 int면 불합격, long이면 합격인 이유

⬆️ 클릭하면 그 이유에 대한 설명으로 이동됨

🔷 그림출처

구글플레이사이트의 김시현님의 콜라츠 추측 계산기어플 보러가기 클릭! 🖱️