- [프로그래머스 / JAVA] Level 2 메뉴 리뉴얼 (72411)
- [프로그래머스 / JAVA] Level 2 행렬 테두리 회전하기 (77485)
- [프로그래머스 / JAVA] Level 2 짝지어 제거하기 (12973)
- [프로그래머스 / MySQL] Level 2 루시와 엘라 찾기 (59046)
- [프로그래머스 / MySQL] Level 2 고양이와 개는 몇 마리 있을까 (59040)
- [프로그래머스 / JAVA] Level 2 타겟 넘버 (43165)
- [프로그래머스 / JAVA] Level 2 더 맵게 (42626)
- [프로그래머스 / JAVA] Level 2 기능개발 (42586)
- [프로그래머스 / JAVA] Level 2 124 나라의 숫자 (12899)
- [프로그래머스 / JAVA] Level 2 멀쩡한 사각형 (62048)
- [프로그래머스 / JAVA] Level 2 단체사진 찍기 (1835)
- [프로그래머스 / JAVA] Level 2 카카오프렌즈 컬러링북 (1829)
- [프로그래머스 / JAVA] Level 2 오픈채팅방 (42888)
- [프로그래머스 / JAVA] Level 2 문자열 압축 (60057)
- [프로그래머스 / JAVA] Level 1 직사각형 별찍기 (12954)
- [프로그래머스 / JAVA] Level 1 x만큼 간격이 있는 n개의 숫자 (12954)
- [프로그래머스 / JAVA] Level 1 행렬의 덧셈 (12950)
- [프로그래머스 / JAVA] Level 1 핸드폰 번호 가리기 (12948)
- [프로그래머스 / JAVA] Level 1 하샤드 수 (12947)
- [프로그래머스 / JAVA] Level 1 평균 구하기 (12944)
👀 [프로그래머스 / JAVA] Level 1 콜라츠 추측 (12943)
- [프로그래머스 / JAVA] Level 1 최대공약수와 최소공배수 (12940)
- [프로그래머스 / JAVA] Level 1 짝수와 홀수 (12937)
- [프로그래머스 / JAVA] Level 1 제일 작은 수 제거하기 (12935)
- [프로그래머스 / JAVA] Level 1 정수 제곱근 판별 (12934)
- [프로그래머스 / JAVA] Level 1 정수 내림차순으로 배치하기 (12933)
- [프로그래머스 / JAVA] Level 1 자연수 뒤집어 배열로 만들기 (12932)
- [프로그래머스 / JAVA] Level 1 자릿수 더하기 (12931)
- [프로그래머스 / JAVA] Level 1 이상한 문자 만들기 (12930)
- [프로그래머스 / JAVA] Level 1 약수의 합 (12928)
- [프로그래머스 / JAVA] Level 1 시저 암호 (12926)
- [프로그래머스 / JAVA] Level 1 문자열을 정수로 바꾸기 (12925)
- [프로그래머스 / JAVA] Level 1 수박수박수박수박수박수? (12922)
- [프로그래머스 / JAVA] Level 1 소수 찾기 (12921)
- [프로그래머스 / JAVA] Level 1 서울에서 김서방 찾기 (12919)
- [프로그래머스 / JAVA] Level 1 문자열 다루기 기본 (12918)
- [프로그래머스 / JAVA] Level 1 문자열 내림차순으로 배치하기 (12917)
- [프로그래머스 / JAVA] Level 1 문자열 내 p와 y의 개수 (12916)
- [프로그래머스 / JAVA] Level 1 문자열 내 마음대로 정렬하기 (12915)
- [프로그래머스 / JAVA] Level 1 두 정수 사이의 합 (12912)
- [프로그래머스 / JAVA] Level 1 나누어 떨어지는 숫자 배열 (12910)
- [프로그래머스 / JAVA] Level 1 같은 숫자는 싫어 (12906)
- [프로그래머스 / MySQL] Level 1 상위 n개 레코드 (59405)
- [프로그래머스 / JAVA] Level 1 다트 게임 (17682)
- [프로그래머스 / MySQL] Level 1 여러 기준으로 정렬하기 (59404)
- [프로그래머스 / JAVA] Level 1 가운데 글자 가져오기 (12903)
- [프로그래머스 / JAVA] Level 1 비밀지도 (17681)
- [프로그래머스 / JAVA] Level 1 부족한 금액 계산하기 (82612)
- [프로그래머스 / MySQL] Level 1 동물의 아이디와 이름 (59403)
- [프로그래머스 / JAVA] Level 1 나머지가 1이 되는 수 찾기 (87389)
- [프로그래머스 / JAVA] Level 1 최소직사각형 (86491)
- [프로그래머스 / MySQL] Level 1 어린 동물 찾기 (59037)
- [프로그래머스 / JAVA] Level 1 2016년 (12901)
- [프로그래머스 / MySQL] Level 1 아픈 동물 찾기 (59036)
- [프로그래머스 / JAVA] Level 1 두 개 뽑아서 더하기 (68644)
- [프로그래머스 / MySQL] Level 1 이름이 있는 동물의 아이디 (59407)
- [프로그래머스 / JAVA] Level 1 두 개 뽑아서 더하기 (12982)
- [프로그래머스 / JAVA] Level 1 예산 (12982)
- [프로그래머스 / JAVA] Level 1 3진법 뒤집기 (68935)
- [프로그래머스 / JAVA] Level 1 약수의 개수와 덧셈 (77884)
- [프로그래머스 / JAVA] Level 1 실패율 (42889)
- [프로그래머스 / JAVA] Level 1 폰켓몬 (1845)
- [프로그래머스 / MySQL] Level 1 이름이 없는 동물의 아이디 (59039)
- [프로그래머스 / MySQL] Level 1 최댓값 구하기 (59415)
- [프로그래머스 / MySQL] Level 1 모든 레코드 조회하기 (59034)
- [프로그래머스 / JAVA] Level 1 체육복 (42862)
- [프로그래머스 / JAVA] Level 1 모의고사 (42840)
- [프로그래머스 / JAVA] Level 1 완주하지 못한 선수 (42576)
- [프로그래머스 / JAVA] Level 1 소수 만들기 (12977)
- [프로그래머스 / JAVA] Level 1 음양 더하기 (76501)
- [프로그래머스 / JAVA] Level 1 K번째수 (42748)
- [프로그래머스 / JAVA] Level 1 내적 (70128)
- [프로그래머스 / JAVA] Level 1 없는 숫자 더하기 (86051)
- [프로그래머스 / JAVA] Level 1 크레인 인형뽑기 게임 (64061)
- [프로그래머스 / JAVA] Level 1 키패드 누르기 (67256)
- [프로그래머스 / JAVA] Level 1 숫자 문자열과 영단어 (81301)
- [프로그래머스 / JAVA] Level 1 신규 아이디 추천 (72410)
- [프로그래머스 / JAVA] Level 1 로또의 최고 순위와 최저 순위 (77484)
콜라츠 추측 🔗
🔗 콜라츠 추측
문제 설명 🔗
1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.
- 입력된 수가 짝수라면 2로 나눕니다.
- 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
- 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.
예를 들어, 입력된 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution
을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.
제한 사항 🔗
- 입력된 수,
num
은 1 이상 8000000 미만인 정수입니다.
입출력 예 🔗
n | result |
---|---|
6 | 8 |
16 | 4 |
626331 | -1 |
입출력 예 설명 🔗
입출력 예 #1
문제의 설명과 같습니다.
입출력 예 #2
16 -> 8 -> 4 -> 2 -> 1 이되어 총 4번만에 1이 됩니다.
입출력 예 #3
626331은 500번을 시도해도 1이 되지 못하므로 -1을 리턴해야합니다.
풀이 🔗
콜라츠 추측이라는 연산을 통해 모든 수를 1로 만들어보자. 단, 500번 이상의 연산이 수행될 경우, 그냥 -1을 반환한다.
- 입력된 수가 짝수라면 2로 나눕니다.
- 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
- 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.
콜라즈 추측의 수행 방법은 위와 같이 매우 간단하다.
위 연산을 반복하는 알고리즘을 구현하자.
케이스 3이 -1이 아니라 488이 나올 경우
케이스 3이 -1인 것과는 달리 실제로 수행해보면 제대로 연산했음에도488
이 나오는 경우가 있다.
이는 초기 함수의 잘못된 표기로 인해 발생한다. 초기 함수는public int solution(int num)
로 되어있지만,num
은int
가 아니라long
으로 선언해야 오류가 없다.num
이int
일 경우 연산 과정에서int
의 최대값(약 21억)을 초과하게 되어, 숫자가 짤려 연산이 뒤틀리게 된다. 따라서public int solution(long num)
으로 바꾸기만하면 정상적으로 동작할 것이다.
코드 🔗
JAVA
0 | /** |
1 | * 콜라츠 추측 클래스 |
2 | * |
3 | * @author RWB |
4 | * @since 2021.12.13 Mon 21:34:17 |
5 | */ |
6 | class Solution |
7 | { |
8 | /** |
9 | * 해답 반환 메서드 |
10 | * |
11 | * @param num: [long] 정수 |
12 | * |
13 | * @return [int] 해답 |
14 | */ |
15 | public int solution(long num) |
16 | { |
17 | int count = 0; |
18 | |
19 | while (num != 1) |
20 | { |
21 | // 500번 수행했을 경우 |
22 | if (count == 500) |
23 | { |
24 | count = -1; |
25 | |
26 | break; |
27 | } |
28 | |
29 | num = num % 2 == 0 ? num / 2 : num * 3 + 1; |
30 | |
31 | count++; |
32 | } |
33 | |
34 | return count; |
35 | } |
36 | } |
📆 작성일
2021-12-18 Sat 12:39:51
📚 카테고리
🏷️ 태그