문제
숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.
각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.
예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.
기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.
나의 풀이
첫 번째 시도
class Solution { fun solution(number: Int, limit: Int, power: Int): Int { var mulist = MutableList(number + 1) { 0 } //number 개수의 기사단원 생성 for (i in 1 .. number) { //기사 단원을 한 명씩 돌면서 for (j in 1 .. i) { if (i % j == 0) mulist[i]++ //약수가 있으면 } if (mulist[i] > limit ) mulist[i] = power //제한 수치를 넘으면 } return mulist.sum() } }
- 이렇게 코드를 짜면 답은 나온다. 다만, 시간 초과가 되어 결국 66.7점으로 통과는 못했다.
- 문제는
for(j in 1 .. i)부분인데, i부터 j사이의 모든 수를 다 돌면서 검사를 하니 i가 클 경우에는 처리량이 많아지는 것이었다.
이를 해결하기 위해 구글링을 했는데, 내가 접근한 키워드는 아래 2개 였다.
1. 약수 효율적으로 구하기
2. 약수 개수 효율적으로 구하기
검색을 해보니, 시간복잡도 얘기가 나오면서 약수의 개수를 구할 때에는 개수를 구할 n에 대해, 1부터 n까지가 아닌 제곱근n까지만 검사를 해도 잘 구할 수 있다는 것을 알 수 있었다. 다만, 1~3 사이의 숫자와 제곱근이 정수인 수에 대해서는 별도의 처리가 필요했다. 이를 코드에 녹인 것이 두 번째 시도이다.
두 번째 시도
class Solution { fun solution(number: Int, limit: Int, power: Int): Int { var mulist = MutableList(number + 1) { 0 } //number 개수의 기사단원 생성 for (i in 1 .. number) { //기사 단원을 한 명씩 돌면서 if (i == 1) { mulist[i] = 1 } else if (i == 2 || i == 3) { mulist[i] = 2 } else { var temp = kotlin.math.sqrt(i.toDouble()).toInt() for (j in 1 .. temp) { if (j * j == i) mulist[i]++ else if (i % j == 0) mulist[i] += 2 } } if (mulist[i] > limit ) mulist[i] = power } return mulist.sum() } }
- 제곱근 까지만 검사하기
- 제곱근n의 약수를 구하여 약수의 수에 2를 곱하기
- 단, 제곱근n의 값이 정수로 떨어지면 2를 곱하는 게 아니라 약수의 수에 1을 더하기
위 문제를 풀면서 같이 언급되는 시간복잡도에 대해서 정리하자면,
시간복잡도
- 알고리즘이 입력 크기에 대헤 어떻게 실행 시간이 증가하는지를 설명하는 것이다. 일반적으로 알고리즘의 효율성을 평가하는 데 사용된다.
- 주로 Big O 표기법을 사용한다.
- Big O 표기법 : 최악의 경우 시간복잡도. 최대한 이 정도의 시간이 걸릴 것이라는 것을 나타낸다.
- Omega 표기법 : 최상의 경우 시간복잡도. 최소한의 시간을 나타낸다.
- Theta 표기법 : 평균적인 경우의 시간복잡도. 최선과 최악의 경우가 서로 같은 경우에 사용된다.
일반적인 시간 복잡도의 예시
- O(1) : 상수 시간. 입력 크기에 관계없이 항상 일정한 실행 시간을 갖는 알고리즘이다.
- 배열에서 요소를 직접 참조하는 것
- O(log n) : 로그 시간. 입력 크기에 대해 로그 함수의 형태로 실행 시간이 증가하는 알고리즘이다.
- 이진 탐색 알고리즘
- O(n) : 선형 시간. 입력 크기에 비례하여 선형적으로 실행 시간이 증가하는 알고리즘이다.
- 배열을 한 번 훑는 것과 같이 각 요소를 한 번씩만 처리하는 경우
- O(n log n) : 선형 로그 시간. 입력 크기에 대해서 선형과 로그 함수의 곱으로 실행 시간이 증가하는 알고리즘이다.
- 퀵 정렬, 병합 정렬
- O(n^2) : 제곱 시간. 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘이다.
- 이중 반복문
- O(2^n) : 지수 시간. 입력 크기에 대해 지수 함수의 형태로 실행 시간이 증가하는 알고리즘이다.
- 모든 부분 집합을 생성하는 경우
- O(n!) : 팩토리얼 시간. 입력 크기의 팩토리얼에 비례하여 실행 시간이 증가하는 알고리즘이다.
- 모든 순열을 생성하는 경우
약수 구하기의 시간 복잡도
- 첫 번째 시도 : O(n^2)
- n이 증가함에 따라 n^2 만큼 증가한다.
- 두 번째 시도 : O(n*√n)
- n이 증가함에 따라 √n만큼 증가한다.
느낀점
- 코딩테스트 연습문제를 순차적으로 풀어나가고 있는데, 점점 각잡고 시간복잡도를 고려해야하는 문제들이 나오는 것 같다. 사실 시간복잡도에 대한 정의, 종류들을 살펴보는 것보다는 그래서 어떻게 하면 반복문을 최소한으로 돌면서 답을 구할 건데? 라는 답에 대답을 할 줄 알아야하는데, 아직 그 역량이 부족한 것 같다.
- 특히 이번 문제에서는 제곱근까지만 반복하면 된다는 흐름을 알고 있었으면 보다 쉽게 풀어낼 수 있었을 터인데.. 전혀 생각을 하지 못했다. 다행히도 선조님들이 정리를 잘 해두신 덕분에 조금만 검색을 해도 해결책을 찾을 수 있었지만, 앞으로는 그 해결책이 내 머릿속에서 바로바로 나왔으면...한다. 그러려면 지금은 다양한 문제와 알고리즘을 풀이법을 접해보면서 지식을 쌓아가야할 것 같다.
- 캠프가 끝나면 알고리즘 책도 한 번 봐야겠다.
[TIL-240314]
