[JAVA] 콜라츠 추측

태로미·2023년 9월 12일
0

Programmers

목록 보기
12/29
post-thumbnail

❓문제


1937년 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 미만인 정수입니다.


💻입출력 예


nresult
68
164
626331-1

입출력 예 #1
문제의 설명과 같습니다.
입출력 예 #2
16 → 8 → 4 → 2 → 1 이 되어 총 4번 만에 1이 됩니다.
입출력 예 #3
626331은 500번을 시도해도 1이 되지 못하므로 -1을 리턴해야 합니다.














📝해결


while문 사용하기

class Solution {
	public int solution(long num) {
        
		int count = 0;
		
		while(num != 1) {
			// 500번 수행했을 경우
			if(count == 500) {
				count = -1;
				break;
			}
			num = num%2 == 0? num/2 : num*3+1;
			count++;
		}

		return count;
	}
}
  • 문제는 int 파라미터를 받게 되어있지만 실제론 long으로 놓고 풀어야 함.
    • int의 경우 연산 과정에서 21억을 넘게 되므로 이 과정에서 연산값 제한으로 계산이 뒤틀림.
  • 숫자가 클수록 500번 횟수 안에서 홀수일 때 3을 곱하는 과정에서,
    처음에 int 범위 안에 있던 num이 계속 곱해지고 나눠지고 반복하다가
    21억이 넘을 수 있음.
    • ex ) num이 700만대일때 연산 과정을 거치다 만약 홀수라면
      3을 곱해야하는데 이 때 무조건 21억이 넘게됨.
  • num이 1이라면 0을 return해야 하므로 count의 초기값을 0으로 잡고, while문의 조건은 num이 1이 아닐 경우로 설정.
  • while문을 돌 때마다 count값이 증가하는데 count가 500일 경우,
    -1 return하고 break문을 만나 whiel문 종료.
  • num이 짝수라면 2를 나누고, 홀수라면 3을 곱한뒤 1을 더해서 num에 다시 저장, count값 1증가.






💭마무리

  • Level_1 / 24:05
  • Point
    – 데이터타입의 범위

int타입과 long타입의 범위 신경쓰기
어찌보면 참으로 당연한건데 평소에 long타입을 잘 쓰지 않아 간과했던 것ㅠㅠ,,,
지금도 프로젝트 리팩토링을 하면서 int타입을 썼으면 썼지 long타입은 아예 사용을 안해서 두 타입의 범위에 대한 부분을 놓쳤다...!!!!😱😱😱
어쩐지 자꾸 에러가 나더라ㅎㅎㅎ;;;ㅎㅎㅎㅎ;;;;
데이터타입의 범위만 인지하고 있었어도 금방 풀 수 있었던 문제~~아쉽다🥹,,,


profile
Here And Now

0개의 댓글