프로그래머스 Level2, N개의 최소 공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

 

입출력 예

arr                                          result

[2,6,8,14]	168
[1,2,3]	6

 

 

 

 

풀이아이디어

기존에 최소공배수, 최대공배수를 구하는 문제에서는 숫자가 2개만 주어졌을 때, 답을 구하는 형식이었는다.

기존 문제들과 다른 점이라면 이 문제는 한 리스트 안에 여러 숫자가 주어진 후, 여러 숫자들의 최소공배수를 구하는 문제였다. 문제를 다 풀고난 후, 다른 분들의 풀이를 보면서 math를 이용하거나 숫자의 크기를 비교하여 정답을 찾는 분들이 있었지만 나는... 맨땅의 해당이랄까..?

 

처음에 여러 방법을 생각해 보다가, 각 주어진 숫자들로 특정 숫자를 나누었을 때, 나머지가 0이 된다면 최소공배수가 될 수 있다는 아이디어를 가지고 풀이를 했다.

 

변수 LCM을  주어진 arr 리스트 숫자들로 나눴을 때, 0으로 떨어지지 않는 경우가 있으면  1을 더 해주고 for 문을 나간다.

다시 while 문을 돌면서 변수 LCM이 리스트 안의 모든 숫자들로 나누어 질 때까지 1을 더하고, 모두 나눠진다면 LCM을 return 해준다. 

 

최종 정답처리는 되었지만... 아무래도 while 문을 돌면서 LCM을 1씩 더해주는 탓에.. 리스트 안에 숫자가 많다면 오래 걸리는 것 같다... 만약에 다음에 이 문제를 풀게된다면.. 다른 분들처럼 풀어볼 수 있을지도..? 현실적으로 코딩테스트 때(물론 이 정도 수준의 문제가 나오진 않겠지만) 나는 이 방법을 먼저 떠올릴 것 같지만... 그때까지 좀더 나를 갈고 닦아보아요..