생각보다 어려운 용어 정리
오늘은 크게 CS 수업 듣기, Level 4 웹 용어 정리하기 조사 두 가지를 했다.
CS는 당연히 지금 듣는 CPU 파트만 해도 어지러운 키워드도 많고 설명 범위가 커서 어지럽고, 웹 용어도 이전의 익숙함에서 벗어나서 심화과정에 들어선 것 같은 키워드가 많이 나오다보니 여태까지의 모토였던 쉽게 설명하기를 실천하려다 보면 내 머리가 먼저 혼란이 오는 상황이 발생하고 있다.
내가 맡은 부분은 Sync-Async, AJAX 인데 동기-비동기부터 이미 내가 실무에서 쓰던 것보다 많은 범위를 학습해야해서 이랬구나 저랬구나를 실감하고 있다.
다행히도 레퍼런스는 넘쳐나고 ChatGPT, 구글링, 추가로 오늘은 Bing 의 Microsoft Copilot 까지 모두 섞어가며 더블 체크를 해서 작성하고 있다. 문제는 이래도 틀린 부분이 있을 것 같다는 점인데 최대한 잘못 전달하는 일 없게 잘 해결하자.
약수의 개수와 덧셈
두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.
fun solution(left: Int, right: Int): Int {
var answer: Int = 0
for (i in left..right) {
answer += if (i.divisorCount() % 2 == 1) i * -1 else i
}
return answer
}
fun Int.divisorCount(): Int {
var count = 0
val sqrt = Math.sqrt(this.toDouble()).toInt()
for (i in 1..sqrt) {
if (this % i == 0) {
count += if (i * i == this) 1 else 2
}
}
return count
}문제의 해결이 난해할 것 같진 않으니 가장 먼저 '약수의 개수 구하는 가장 효율적인 방법'을 찾았다.
아무래도 수학적인 부분이라 스스로 떠올리기엔 부족했고 찾아낸 방법을 이해할 수 있으면 차라리 다행이었다.
다행히도 찾아낸 방법은 비교적 쉬웠다:
약수의 개수는 제곱근 이하의 수만 찾아내고 나머지 절반을 찾으면 된다는 것이었다.
이러면 시간 복잡도가 O(n) 에서 O(root(n))이 되기에 획기적으로 반복 횟수를 줄일 수 있었다.
증명 참고
찾아낸 방법으로 함수를 만들었는데 그 중 핵심은 Int를 확장한 함수로 따로 빼냈다.
핵심은 제곱근 미만의 약수가 있으면 2개씩 존재한다 랑 제곱수라면 1개만 존재한다 인 것 같아서 count 조건문에 해당 방식으로 처리하니 잘 동작했다.
코드가 조금 길지 않나 싶어 다른 사람들의 풀이도 참고했다.
fun solution2(left: Int, right: Int): Int = (left..right).map { i -> if ((1..i).filter { i % it == 0 }.size % 2 == 0) i else -i }.sum()For문의 명시적 사용 없이 단일 표현식으로 제출한 깔끔한 코드라 나도 참고해봤는데 실행 시간이 상당히 차이가 났다. 반복 횟수의 차이가 가장 큰 원인같았다.
그래서 나도 위 답안을 참고해서 코드를 간결하게 타협해봤다.
fun solution3(left: Int, right: Int): Int = (left..right).map { i -> if (i.divisorCount() % 2 == 0) i else -i }.sum()만들어두었던 divisorCount 를 사용해서 반복 횟수를 절감했더니 실행 시간은 좀 줄일 수 있었다.
그래도 최초 답안보다는 여전히 실행시간이 꽤 긴 편인지라 퍼포먼스를 고려해야 한다면 최초 답안을 사용하는 것이 맞을 듯 싶다.
