left ~ right까지 약수의 개수를 구하고, 약수의 개수가 짝수라면 그 수들을 더하고, 홀수라면 빼는 로직으로 해결해야 한다.
약수란 어떤 수로 나누었을 때 나머지가 0이 되는 수 1은 모든 수의 약수가 된다. 약수를 구하는 로직을 살펴보자.
// number의 약수
function getDivisor(number) {
const result = [];
for(let i = 1; i <= number; i++){
if(i % number === 0){
result.push(i) // [1,...,number]
}
}
} - 기본적인 방법으로 O(n)의 시간 복잡도를 가지며, 인자의 값이 커질록 처리 시간도 증가한다.
- 효율적인 방법은 아니기 때문에 *제곱근 방식으로 다시 풀어봐야겠다.
약수를 구했다면 개수가 짝수인지 홀수인지를 확인해야 한다.
그 전에 문제 해결을 위한 데이터 구조를 먼저 생각해보도록 하자.
13의 약수 : 1, 13
14의 약수 : 1, 2, 7, 14
...
n의 약수 : 1,..n
데이터에는 타켓 숫자와 약수의 개수를 함께 저장해야 한다.
왜냐하면, 약수 개수의 짝/홀수의 유무 확인과 그에 따른 증감 연산이 가능하기 때문이다.
따라서 아래와 같은 구조가 필요하고, 이를 위해 Map 객체를 사용하였다.
[{13 : [1, 13]}, {14 : [1, 2, 7, 14]}, 15 : [1, 3, 5, 15]]function solution(left, right) {
var answer = 0;
const arrMap = new Map()
let divisors = []
// 1) left~ right 증감하며 loop 탐색
for(let i = left; i <= right; i++){
// 2) 약수 서칭
for(let j = 1; j <= i; j++){
if(i % j === 0){
divisors.push(j) // ex :[1, 2, 4, 8, 16]
}
}
arrMap.set(i, divisors) // [13 : [1, 13]] 로 저장
// 3) 배열 초기화-> i값에 따른 약수 배열을 세팅하기 위함
divisors = []
// 4) 짝/홀 수에 따른 결과값 증감 연산
if(arrMap.get(i).length % 2 === 0){
answer += i
}else {
answer -= i
}
}
return answer;
}- new Map() 을 통해 새로운 map 객체를 생성하고, arrMap.set() 구문으로 key : 현재 loop의 타켓(i), value : 약수의 리스트인 divisors 를 세팅한다.
- arrMap 데이터 내에 key값에 따른 value(약수 리스트)의 크기가 짝수라면 key값을 더하고, 홀수일 땐 뺀다.
- i번째의 약수 개수 세팅이 다 끝나면 i+1번째 약수를 세팅하기 전에 배열 리스트를 초기화시켜 올바른 데이터가 담기도록 한다.
Map()
[key, value] 로 그룹화 된 배열을 return하며, set() 된 key의 순서대로 저장하고 저장된 순서대로 호출된다. key값은 중복될 수 없기 때문에 '중복 제거'가 가능하다.
Map 객체는 key-value를 한쌍으로 하는 배열을 return하기 때문에 구현하고자 했던 데이터의 구조 [{key, value}] -> [[key, value]] 와는 상이했다.
[{}] 로 세팅하려면 어떤 내장 객체 혹은 함수를 사용해야 할까 다시 한번 고민이 필요한 시점이다.
문제를 풀면서 데이터 가공 능력 스킬이 부족하다는 생각이 든다.
API 통신으로 서버에서 받아온 데이터를 가공하고 화면 구조에 알맞게 매핑하는 것이 프론트앤드 개발의 꽃인데 말이다..
한 문제, 두 문제 계속 풀다보면 내공이 쌓이겠지?
답답하지만 어제보다 조금 더 발전한 기분(?)으로 버티는 중이다.
참고 사이트
