![thumbnail](https://blog.kakaocdn.net/dn/bP07lP/btsClIHFoKx/KgjKoJCGA8nNlHhv55JrSk/img.png)
안녕하세요. 이번에는 프로그래머스 N개의 최소 공배수 문제를 풀어보려고 합니다.
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
Problem
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
[제한 사항]
○ arr은 길이 1 이상, 15 이하인 배열입니다.
○ arr의 원소는 100 이하인 자연수입니다.
![](https://blog.kakaocdn.net/dn/cWR42w/btsCezeS3co/Nyl5QOPyKx8w8XonR74IeK/img.png)
Solution
import kotlin.math.*
class Solution {
fun solution(arr: IntArray): Int {
var answer = arr[0]
(1 until arr.size).map {
answer = answer * arr[it] / getGcd(max(answer, arr[it]), min(answer, arr[it]))
}
return answer
}
tailrec fun getGcd(a: Int, b: Int): Int {
return if(b == 0) a else getGcd(b, a % b)
}
}
이번에는 최소 공배수를 구하는 getGcd를 꼬리재귀 함수로 구현해 주었습니다. 여기서 꼬리재귀가 궁금하시다면, 아래의 링크로 들어가면 됩니다.
[Kotlin] tailrec 꼬리 재귀 함수에 대하여 알아보기
Tailrec(꼬리 재귀)란, 재귀 함수 내부의 재귀 호출에서 반환된 결괏값을 갖고 어떤 추가 연산도 수행하지 않으며 즉시 반환하는 식으로 작성된 재귀 함수를 꼬리 재귀(tail recursion) 함수라 합니다.
echung93.tistory.com
answer을 두 수의 최소 공배수로 만들면서 문제를 해결할 수 있었습니다.
1. 다른 사람 코드
class Solution {
fun solution(arr: IntArray): Int {
var answer = 1
while(true) {
var x = 0
for(a in arr) x += answer%a
if(x==0) return answer
answer++
}
return answer
}
}
저의 코드와 다르게 반복문으로 푼 문제가 있어서 가져와봤습니다.
코드 분석
1. x를 0으로 초기화해줍니다.
2. answer의 값이 배열의 값으로 나누어 떨어지는지 확인합니다.
3 - 1. 여기서 만약 모든 값이 떨어지면 최소 공배수의 값이므로 return 해줍니다.
3 - 2. 만약 값이 떨어지지 않는다면 answer을 증가시키고 다시 1 ~ 3번의 작업을 반복해 줍니다.
이렇게 while문을 통해서 구현하는 방법이 있다. 하지만 최소 공배수의 값이 커질수록 반복되는 횟수가 많아지기 때문에 속도 면에서 재귀 함수보다 좀 더 시간 복잡도면에서는 효율적이라고 생각됩니다. 다른 의견이나 다른 방법이 있으시면 언제든지 편하게 댓글로 가르쳐주시면 감사하겠습니다!
Performance
1. 내가 작성한 코드 | 2. 다른 사람 코드 |
![]() |
![]() |
'프로그래머스 Algorithm' 카테고리의 다른 글
[프로그래머스] 추억 점수 Kotlin (2) | 2023.12.22 |
---|---|
[프로그래머스] 멀리 뛰기 Kotlin (0) | 2023.12.21 |
[프로그래머스] 콜라 문제 Kotlin (2) | 2023.12.19 |
[프로그래머스] 예상 대진표 Kotlin (2) | 2023.12.18 |
[프로그래머스] 두 개 뽑아서 더하기 Kotlin (2) | 2023.12.17 |