개발의 흔적

알고리즘 테스트# 6. 콜라츠 추측 본문

코딩테스트 연습

알고리즘 테스트# 6. 콜라츠 추측

남들에게 도움을 주는 백엔드 개발자가 되자 2020. 7. 20. 11:58

안녕하세요.

 

프로그래머스에 있는 "콜라츠 추측" 알고리즘 문제를 풀어보겠습니다.

 

문제 : 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.

 

출력 : 

 

6 8
16 4
626331 -1

 

코드 :

 

 

 

* 문제 해설 *

 

입력된 정수의 값이 1이 될때까지 반복을 시킵니다.

 

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

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

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

 

그후 반복된 값에 대해선 count를 줍니다.

 

정수  : 6 

 

6 % 2 = 3

3 * 3 + 1 = 10

10 % 2 = 5

5 * 3 + 1 =16

16 % 2 = 8

8 % 2 = 4

4 % 2 = 2

2 % 2 = 1

 

입력받은값에 값을 계속 넣기때문에 큰수인경우네는 오버플로우가 발생할수있기에 타입을 바꿔줘야합니다.

 

* 코드 해설 *

 

반복하는 횟수를 모르기에 while문으로 진행합니다.

조건은 ( num != 1 ) num의값이 1이 아닌경우 논리적으로 false값이 되기때문에 while문을 계속 반복합니다.

그후 num != 1의 값이 true가 될 경우 while문은 빠져나옵니다.

입력값이 홀수인지 짝수인지를 판별합니다. ( num % 2 == 0 ) 짝수일경우 %2 홀수일경우 *3 + 1

을 합니다.

그후 결과가 나옵니다.

단 여기서 656321의 값이 1이될때까지 계속 반복한다하면 곱셈으로 인해 int값의 범위를

넘어갈껍니다. 넘어가게되면 쓰레기 값이 나오기떄문에 정상적인 결과값이 안나옵니다.

왜냐 num의 값은 입력받은 값 동시에 곱해진 값도 순차적으로 쌓이기 떄문입니다.

그렇기에 작은값만 생각하지말고 큰수를 생각해야합니다.

int -> 4byte

long -> 8byte

즉 long을 사용해야합니다.

여러가지 테스트 케이스가 나올수있기때문에 로직은 맞는거같은데 만약 결과가 이상하다싶으면

범위값을 생각해야합니다.

 

 

 

더좋은 소스있으면 공유바랍니다.

 

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

 

Comments