[Python] 콜라츠 추측(프로그래머스/python/Level 1)

안녕하세요! 데코입니다!

 

오늘은 프로그래머스 코딩테스트 연습에 있는 "콜라츠 추측" 문제를 포스팅하려고 합니다!

 

바로 포스팅 시작할게요! :)

(출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12943)

 

---

 

1. 문제 :  콜라츠 추측(Lv. 1)

 

---

 

2. 문제 설명

 

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

 

[ 입출력 예 ]

 

n	result
6	8
16	4
626331	-1

 

[ 입출력 예 설명 ]

 

입출력 예 #1
문제의 설명과 같습니다.

입출력 예 #2
16 → 8 → 4 → 2 → 1 이 되어 총 4번 만에 1이 됩니다.

입출력 예 #3
626331은 500번을 시도해도 1이 되지 못하므로 -1을 리턴해야 합니다.

 

---

 

3. 문제 풀이

# 1안
def solution(num):
    answer = 0
    while(True):
        if num == 1:
            return 0
        if num != 1:
            if num%2==0:
                num = num/2
                answer += 1
                if num == 1:
                    return answer
            else :
                num = (num*3)+1
                answer += 1
                if num == 1:
                    return answer
        if answer == 500:
            return -1
    return answer

 

문제 설명에 맞는 코드를 작성하기 위해서 1안으로 작성했습니다!

 

#  1안 풀이 설명

# [ 문제 풀이 설명 ]

 

문제와 입출력 예시를 보며, 입력된 수 num에 따라 반목문이 몇 번 실행되어야 하는지 모르는 상태이기 때문에

 

while 반복문 실행이 필요하다고 생각을 했습니다!

 

while(True)를 통해 결과 값을 return 해줄 때까지 반반복문을 실행해 주었습니다.

 

콜라츠 추측을 실행하는 횟수를 구하는 것이 최종 목표이기 때문에,

 

연산 횟수를 저장하는 answer 변수를 초기값 0으로 선언하였습니다.

 

if 문으로 1이 아닌 경우에는

 

num의 값을 2로 나누어 나머지 확인 하는 작업을 통해 짝수 혹은 홀수 인지를 판별하였고

 

짝수인 경우는 2로 나누고, 홀수인 경우는 3을 곱한 뒤 1을 더합니다.

 

또한 작업이 500번 이상 반복된다면 -1로 반환을 하라는 조건을 코드에 추가하였습니다!

 

모든 연산이 종료되면, answer를 return 해주었습니다.

 

 

num = 32를 예로 들어볼게요!

 

처음에 answer=0으로 선언해주고

 

while 반복분을 실행합니다!

 

answer=0, num=32 > num이 1이 아니므로 홀짝 판별 > 짝수 > num = num/2 = 16 > answer = 1

 

answer=1, num=16 > num이 1이 아니므로 홀짝 판별 > 짝수 > num = num/2 = 8 > answer = 2

 

answer=2, num=8 > num이 1이 아니므로 홀짝 판별 > 짝수 > num = num/2 = 4 > answer = 3

 

answer=3, num=4 > num이 1이 아니므로 홀짝 판별 > 짝수 > num = num/2 = 2 > answer = 4

 

answer=4, num=2 > num이 1이 아니므로 홀짝 판별 > 짝수 > num = num/2 = 1 > answer = 5

 

answer=5, num=1 > num이 1이므로 반목분 실행 종료

 

이후 answer 변수를 return 해주었습니다!

 

= 5

 

# 1안

def solution(num):
    # answer 및 초기값 0 선언
    answer = 0
    # 무한 반복문 수행
    while(True):
        # num이 1인 경우 수행
        if num == 1:
            return 0
        # num이 1이 아닌 경우 수행
        if num != 1:
            # 짝수인 경우 수행
            if num%2==0:
                num = num/2
                answer += 1
                if num == 1:
                    return answer
            # 홀수인 경우 수행
            else :
                num = (num*3)+1
                answer += 1
                if num == 1:
                    return answer
        # answer이 500이 되는 경우 수행
        if answer == 500:
            return -1
    return answer

 

 

---

 

4. 문제 풀이 후기

 

이번 문제는 콜라츠 추측에 관한 문제로, 

 

주어진 수를 규칙에 따라 1을 만들 때까지 소요되는 횟수를 산출하는 문제였습니다. 

 

이번에 푼 문제는 기존의 for 반복문이 아닌 while 반목문을 이용한 것이 특징이네요!

 

while 반복문은 조건식이 참인 동안 계속해서 반복합니다.

 

반복하는 과정에서 return 값이 참이 아닌 값이면(0), 현재 실행 중인 반복문이 즉시 중단됩니다.

 

while 반복문보다는 for 반복문을 자주 이용해서인지 조금 어색했네요!

 

이 외에는 어려운 부분이 없어서 제가 따로 코멘트할 것은 없습니다!

 

---

이번 포스팅은 프로그래머스에 있는

 

python을 이용한 코딩테스트 문제를 풀어보았습니다!

 

너무 쉬운 부분만 있다면 이번 포스팅처럼 다른 풀이 방법도 설명하면서 진행하려고 해요!

 

설명이 어려운 부분 혹은 잘 이해가 안 가는 부분

그리고 더 궁금한 내용이 있다면

언제든지 댓글로 남겨주세요!

빠르게 궁금증을 해결해 드릴게요!

공감과 댓글은 큰 힘이 됩니다!

오늘도 블로그 방문해 주시고

포스팅 읽어주셔서 감사합니다!