937년 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을 완성해 주세요.
단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.
제한 사항)
입력된 수, num은 1 이상 8,000,000 미만인 정수입니다.
문제 설명
특별할것 없이 숫자를 짝수 홀수일 경우를 나눠서 1로 만드는 경우가 되느냐 묻는 문제이다.
기존코드
class Solution {
public int solution(int num) {
int answer = 0;
while(true){
if(num==1){
break;
}else if(answer>500){
answer=-1;
break;
}else{
if(num%2==0){
num= num/2;
answer++;
}else{
num= (num*3+1);
answer++;
}
}
}
return answer;
}
}
몇번,몇십번을 봐도 틀리면 안되는데 자꾸 다르다고 나왔다
정상적으로 동작해서 무조건 동작해야하는데 ???
가장 큰 실수는 제한조건 num이 1이상 800만미만 인 정수입니다
라는 말을 int형의 범위를 넘지 않는다고 혼자 해석해버린 것이다....
오버플로우라는 경우의 수를 아예 제외하고 시작했기 때문에 이 간단한 풀이를 내가 못푸는건가? 내 알고리즘에 뭐가 문제가있지? 내 코딩은 틀려먹은건가? 하면서 자책을 오래했다...
확인해본 결과 입력값 626331일때 103번째로 가는 부분에서 int의 범위 20억을 넘어서서
오버플로우가 발생하는것을 알 수 있다.
overflow로 인해 결과값이 뒤틀려버린것이다..
class Solution {
public int solution(int num) {
int answer = 0;
long number = num;
while(true){
if(number==1){
break;
}else if(answer>500){
answer=-1;
break;
}else{
if(number%2==0){
number= number/2;
answer++;
}else{
number= (number*3+1);
answer++;
}
}
}
return answer;
}
}
해결방법 ) num을 long타입 number로 처리하여 오버플로우를 해결한다 .
특정 상황에 대해 지레짐작하여 배제하고, 또 쉬워보인다고 방심하지 말고 집중해서 풀어야겠다
