문제 설명
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을 리턴해야 합니다.
풀이 과정
- 작업 반복 횟수를 담을 변수 count를 만들어준다.
- 주어진 수는 작업을 반복하는 과정에서 변하기 때문에 변수 number에 담아준다.
- while을 사용해 주어진 수가 1이 아닐 경우 작업 과정을 계속해서 반복하도록 한다.
- while문 안에 if, else를 사용해 짝수일 경우, 홀수일 경우를 나눠서 작업하도록 한다.
- if, else 중 하나가 실행되고 나면 count 값이 1씩 증가하도록 한다.
- count가 500 이상이 되면 -1을 반환하도록 한다.
- count가 500 이상이 되지 않는다면 그대로 count를 그대로 반환!
Solution
func solution(_ num:Int) -> Int {
var count = 0
var number = num // 입력값을 추적하기 위한 변수
while number != 1 { // number가 1이 아닌 동안 반복
if number % 2 == 0 {
number /= 2 // 짝수인 경우
} else {
number = number * 3 + 1 // 홀수인 경우
}
count += 1
if count >= 500 {
return -1 // 500번 이상 반복하면 -1 반환
}
}
return count // 반복 횟수 반환
}Additional
다시 보니까 num이 1일 경우 0을 반환 하라는 조건이 있더라.
그래서 조건을 추가 해줬다!!
func solution(_ num:Int) -> Int {
if num == 1 {
return 0
}
var count = 0
var number = num
while number != 1 {
if number % 2 == 0 {
number /= 2
} else {
number = number * 3 + 1
}
count += 1
if count >= 500 {
return -1
}
}
return count
}Another Solution
‘재귀 함수’ 를 사용한 풀이를 알게 됐다!
처음 알게 된 개념이니까 정리 해보자 :>
재귀함수 Recursive Function
함수가 자기 자신을 호출하는 것!!
원하는 값을 얻기까지 호출을 반복한다.
기본 케이스 Base Case
기본적으로 반복적으로 호출된다. 하지만 어느 시점에서는 호출하지 않고 종료를 해야 하는데, 이런 종료(탈출) 조건을 기본 케이스라고 한다.
재귀 케이스 Recursive Case
함수가 자기 자신을 호출하는 부분을 말한다. 더 작은 값을 사용해 함수를 호출한다.
재귀 케이스만 있고 기본 케이스가 없으면 무한 재귀에 빠지게 된다.
즉 종료 조건이 없으면 계속해서 자기 자신을 호출하게 된다는 이야기!!!
재귀함수를 사용하면 반복을 더 효과적으로 표현할 수 있다!
//큰 틀! 이해는 아래 factorial 예시로 하는 게 더 쉽다.
func recursiveCall(입력) -> 출력 {
if 입력 <= 일정 값 { // 탈출 조건 명시
return 일정값 또는 입력값 또는 특정값
}
return recursiveCall(입력보다 작은 값)
}//예시_factorial
//factorial은 이런 것!! -> n! = n * (n-1)!
func factorial(_ n: Int) -> Int {
if n == 0 {
return 1 // 기본 케이스: 0!은 1
} else {
return n * factorial(n - 1) // 재귀 케이스: n!은 n * (n - 1)!
}
}
print(factorial(5)) // 출력: 120 (5!)
//즉, 이 factorial 함수의 탈출 조건((=기본 케이스))은 n == 0 일 경우
// 그리고 재귀 케이스는 n == 0 이 아닐 경우! 자기 자신(factorial함수)을 호출해서 실행한다.이번 문제를 재귀함수를 사용해서 표현하면 이렇게!
대신 num 값 자체가 1 일 때 0을 반환하는 경우는 포함시킬 수가 없었다.
count를 리턴하는 것과 겹쳐서..! 이 부분은 아직 해결을 못했다. 좀 더 생각해보자.
func solution(_ num: Int, _ count: Int = 0) -> Int {
if num == 1 {
return count
}
if count >= 500 {
return -1
}
if num % 2 == 0 {
return solution(num / 2, count + 1)
} else {
return solution(num * 3 + 1, count + 1)
}
}