코딩
프로그래머스 문제 풀이: 콜라츠 추측 (Level 1)
오늘은 학부생
2025. 3. 22. 13:41
문제 설명
1937년 Collatz에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면 모든 수를 1로 만들 수 있다는 이론입니다.
작업 과정
- 입력된 수가 짝수라면 2로 나눕니다.
- 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
- 결과로 나온 수에 같은 작업을 반복합니다.
- 이 작업을 1이 될 때까지 반복하며, 반복 횟수를 반환합니다.
- 단, 500번 반복해도 1이 되지 않는다면 -1을 반환합니다.
제한 사항
- 입력된 수 num은 1 이상 8,000,000 미만인 정수입니다.
입출력 예시
numresult
| 6 | 8 |
| 16 | 4 |
| 626331 | -1 |
문제 해결: 사고 과정
이 문제를 처음 접했을 때, 반복문을 활용하여 간단한 조건문만으로 해결할 수 있는 문제라고 생각했습니다. 핵심은 주어진 수를 1로 만들기 위한 변환 작업을 몇 번 수행하는지 카운트하는 것입니다.
- 입력값이 1이면 바로 0을 반환해야 합니다. 1은 이미 조건을 충족하기 때문이죠.
- 짝수와 홀수를 구분하여 적절한 연산을 수행하면 됩니다.
- 짝수: num // 2
- 홀수: num * 3 + 1
- 변환 과정을 최대 500번 반복하는 것이 핵심입니다.
- 반복 횟수가 500번을 넘기면 -1을 반환해야 합니다.
- 따라서, while 문을 사용하여 최대 500번까지 반복하도록 설계했습니다.
이러한 사고 과정을 기반으로 코드를 작성해 보았습니다.
나의 코드
def solution(num):
# Step 1. 입력이 이미 1이면 0 반환
if num == 1:
return 0
# Step 2. 콜라츠 변환 작업을 반복 (최대 500번)
count = 0
while num != 1 and count < 500:
if num % 2 == 0: # 짝수일 경우
num //= 2
else: # 홀수일 경우
num = num * 3 + 1
count += 1
# Step 3. 변환 도중 1이 되면 횟수 반환, 아니면 -1
return count if num == 1 else -1실행 예시
print(solution(6)) # 8
print(solution(16)) # 4
print(solution(626331)) # -1
print(solution(1)) # 0다른 사람의 코드 분석
코드 1: for 문 활용
def collatz(num):
for i in range(500):
num = num / 2 if num % 2 == 0 else num * 3 + 1
if num == 1:
return i + 1
return -1사고 과정
- for 문을 사용하여 최대 500번 반복하는 방식으로 접근.
- i + 1을 반환하여 몇 번째 반복에서 1이 되었는지 명확히 표현.
- 다만, / 연산을 사용하여 실수 연산이 발생할 가능성이 있음.
코드 2: while 문을 더 간결하게 작성
def collatz(num):
cnt = 0
while num != 1 and cnt < 500:
num = 3 * num + 1 if num % 2 else num // 2
cnt += 1
return cnt if cnt < 500 else -1사고 과정
- while 문을 활용해 cnt 변수를 증가시키며 1이 될 때까지 반복.
- if-else 문을 한 줄로 간결하게 작성하여 코드 길이를 줄임.
- // 연산자를 사용하여 정수 연산을 유지함.
마무리
콜라츠 추측 문제는 반복문과 조건문을 활용하여 해결할 수 있는 간단한 문제입니다. 하지만 연산 과정에서 효율성과 코드 가독성을 고려하여 작성하는 것이 중요합니다.
배운 점
- while vs. for 문 선택의 차이.
- 정수 연산을 유지하기 위한 // 사용.
- 코드를 간결하게 만드는 조건문 활용 방법.