🔗 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/77884
✅ 풀이
문제가 짧아서 그런가... 제대로 문제도 파악하지 않고 푼 나에게.. 아무리 연습이지만 읽고 파악하자.. 라는 다짐으로 적어본다..
주어진 left, right 사이에 있는 수에 대해 약수의 개수가 짝수 이면 더하고 홀수면 빼서 최종 값을 구하는 문제이다
일단 첫번째로 약수의 개수를 구하는 함수를 만들고 조건문을 통해 짝수와 홀수를 구분해서 최종 값을 구하면 되겠다는 생각이 들었다
⌨️ 첫번째 풀이
import Foundation
func solution(_ left:Int, _ right:Int) -> Int {
var result = 0
for i in left...right {
let count = calculate(num: i)
result += (count % 2 == 0) ? i : -i
}
return result
}
func calculate(num: Int) -> Int{
var count = 0
for i in 1...num {
if num % i == 0 {
count += 1
}
}
return count
}일단 약수를 구하는 함수인 calcualte() 를 만들었다. 사실 약수를 어떻게 구해야하는지 감이 안잡혔다...
그래서 일단 약수를 구하는 수를 1부터 자기 자신까지 반복해서 나눌때 나머지가 0 인수를 구하는 방법을 채택했다
물론 이 방법보다 더 효율적인 방법이 존재할거라 생각했지만 시간을 정해놓고 풀고 있어서 다른 방법이 얼른 떠오르지 않았다..
위의 풀이는 모든 경우를 탐색하므로 O(N)의 시간복잡도를 갖게 되어 수의 범위가 굉장히 크다면 시간 초과로 풀 수 없는 문제가 존재할 것이다....
문제를 푸는데 있어 틀린 방법은 아니지만 일단 다른 풀이를 보며 생각을 해보았다
⌨️ 다른 사람 문제 풀이
import Foundation
func solution(_ left: Int, _ right: Int) -> Int {
return (left...right).map { i in (1...i).filter { i % $0 == 0 }.count % 2 == 0 ? i : -i }.reduce(0, +)
}
역시 swift 는 고차함수를 잘 쓰는게 코드의 양을 확실히 줄일 수 있는거 같다...
이 풀이는 left 부터 right 까지 map 메서드를 통해 해당 범위에 있는 수에 대해 작업을 하게된다
1부터 i 까지의 수 중 filter 메서드를 통해 i 를 각 숫자 $0 으로 나눈 나머지가 0 인 수를 골라내서 약수를 찾아낸다
count 메서드를 통해 약수의 개수를 구하게 되고 짝수라면 i, 홀수면 -i 를 reduce 메서드를 통해 전달받은 i 를 더하게 된다
결국 약수를 구하는 방법은 나와 동일하지만 고차 함수를 통해 코드의 양을 줄인 느낌이다!
코드를 해석하는건 진짜 오래 걸리는 느낌이다...
근데 이게 정말로 효율적인 알고리즘일까?
이번엔 약수를 구하는 다른 방법을 쓴 풀이이다
import Foundation
func solution(_ left:Int, _ right:Int) -> Int {
var answer = 0
for number in left...right{
if floor(sqrt(Double(number))) == sqrt(Double(number)) {
answer -= number
} else {
answer += number
}
}
return answer
}이게 먼가.. 매우 놀랐다..
N의 약수를 구할 때는, 1부터 N의 제곱근 까지의 수만 0으로 나누어 떨어지는지 확인하면 된다!
제곱근을 통해서 약수를 구한다니.. 완전 신기했다..
해당 수의 제곱근의 정수 값까지 반복문을 통해 구한다면 시간복잡도를 O(logN) 까지 줄일 수 있다는 것이다!!
근데 위의 코드는 한번 더 생각을 해야 한다
-
해당 수를 Double 형으로 변환하고 sqrt 메서드를 통해 제곱수를 구한다
-
다시 그 수를
floor메서드를 통해 제곱근을 내림하여 정수 부분을 얻게된다 -
완전 제곱수인 경우 제곱근의 정수 부분과 원래 숫자의 제곱근이 같아야 한다는 것이다
결과적으로, 같다면 약수의 개수는 짝수개, 다르다면 홀수개 라는 의미이다!
내가 써도 이해가 안된다 그럴땐 하나씩 확인을 해보자!
1️⃣ 만약 8 이라 가정을 해보자!
8의 약수는 1,2,4,8 이다
조건문의 첫번째 부분은 2가 나오고 제곱근을 구하면 2√2 로 다르므로 짝수개가 되는 것이다
2️⃣ 이번엔 9로 가정을 해보자!
9의 약수는 1,3,9 이다
조건문의 첫번째는 3이고 제곱근 역시 3이여서 같으므로 홀수개가 되는것이다
참.. 알고리즘 문제를 풀면서 정말 다양한 방법이 존재하고.. 시간 복잡도를 줄일 수 있는 방법을 찾는 것이 신기하다..
위와 같이 제곱근을 통해 약수를 찾는 방법을 몰라도 다르게 방법을 찾는 것도 내 실력인거 같다.. 더 노력하자!
