안녕하세요. 이번에는 프로그래머스 콜라츠 추측을 풀어보려고 합니다.
https://school.programmers.co.kr/learn/courses/30/lessons/12943
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
Problem
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 미만인 정수입니다.
![](https://blog.kakaocdn.net/dn/d6Xc51/btsAmtzOYSN/K6EiajXjMueCJy3hCu3Xpk/img.png)
Solution
class Solution {
fun solution(num: Int): Int {
var answer = 0
var input = num.toLong()
while (input != 1L) {
if(answer == 500) {
answer = -1
break
}
answer++
if(input % 2 == 0L) input = isEven(input)
else input = isOdd(input)
}
return answer
}
fun isEven(num: Long): Long {
return num / 2
}
fun isOdd(num: Long): Long {
return num * 3 + 1
}
}
이번 문제는 짝수일 때와 홀수일 때에 처리하는 함수를 따로 만든 후 while문을 통해서 정답을 구할 수 있도록 코드를 작성하였다.
1. 다른 사람 코드
class Solution {
fun solution(num: Int): Int = collatzAlgorithm(num.toLong(), 0)
tailrec fun collatzAlgorithm(n: Long, c: Int): Int =
when{
c > 500 -> -1
n == 1L -> c
else -> collatzAlgorithm(if(n % 2 == 0L) n / 2 else (n * 3) + 1, c + 1)
}
}
문제를 해결하였지만, 좀 더 나은 코드에 대한 방법이 생각이 나지 않아 다른 사람의 코드를 보고 학습을 진행하였다. Kotlin에서는 trailrec이라는 꼬리재귀의 함수가 있다는 것을 배울 수 있었다. trailerc(꼬리재귀)는 추가적인 연산이 없이 자신 스스로 재귀적으로 호출하다가 어떤 값을 리턴하는 함수를 의미한다. 나중에 꼬리재귀를 학습하면서 블로그에 작성해 봐야겠다.
Performance
1. 내가 작성한 코드 | 2. 다른 사람 코드 |
![]() |
![]() |
'프로그래머스 Algorithm' 카테고리의 다른 글
[프로그래머스] 음양 더하기 Kotlin (0) | 2023.11.18 |
---|---|
[프로그래머스] 서울에서 김서방 찾기Kotlin (0) | 2023.11.17 |
[프로그래머스] 두 정수 사이의 합 Kotlin (0) | 2023.11.15 |
[프로그래머스] 하샤드 수 Kotlin (0) | 2023.11.14 |
[프로그래머스] 정수 내림차순으로 배치하기 Kotlin (2) | 2023.11.13 |