백준 9506번을 풀어보았다.
다양한 풀이가 존재하는데, 크게 약수 구하기, 배열의 합 구하기, 배열 출력하기 측면에서 구분해볼 수 있다.
1. 약수 구하기
- 1부터 n까지 확인
- 1부터 n/2까지 확인
- 1부터 n의 제곱근까지 확인
2. 배열의 합 구하기
- 반복문 이용
- reduce 메소드 이용
3. 배열 출력하기
- 반복문과 조건문 이용
- join 메소드 이용
1. 약수 구하기
1부터 n까지 확인
let input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map(Number)
let output = ''
for (const n of input) {
if (n === -1) break
let sum = 0, divisors = []
for (let i = 1; i < n; i++) {
if (n % i === 0) {
divisors.push(i)
sum += i
}
}
if (sum === n) {
output = '= '
for (let i = 0 ; i < divisors.length; i++) {
i === divisors.length - 1 ? output += `${divisors[i]}` : output += `${divisors[i]} + `
}
} else {
output = 'is NOT perfect.'
}
console.log(`${n}`, output)
}
1부터 n/2까지 확인
let input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map(Number)
let output = ''
for (const n of input) {
if (n === -1) break
let sum = 0, divisors = []
for (let i = 0; i <= n/2; i++) {
if (n % i === 0) {
divisors.push(i)
sum += i
}
}
if (sum === n) {
output = '= '
for (let i = 0 ; i < divisors.length; i++) {
i === divisors.length - 1 ? output += `${divisors[i]}` : output += `${divisors[i]} + `
}
} else {
output = 'is NOT perfect.'
}
console.log(`${n}`, output)
}
이 문제는 완전수 여부를 따지는 문제로, 자기 자신은 divisors에 추가할 필요 없다.
따라서 n의 약수 중 자기 자신을 제외한 가장 큰 약수는
n이 짝수일 경우 2와 짝을 이루는 약수인 n/2, n이 홀수일 경우 최대 n/3로 n/2보다 작으므로
1부터 n/2까지만 반복하여도 자기 자신을 제외한 모든 약수를 구할 수 있다.
1부터 n의 제곱근까지 확인
let input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map(Number)
let output = ''
for (const n of input) {
if (n === -1) break
let sum = 0, divisors = []
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
divisors.push(i)
sum += i
if (i * i !== n && i !== 1) {
divisors.push(n/i)
sum += n/i
}
}
}
divisors.sort((a, b) => a - b)
if (sum === n) {
output = '= '
for (let i = 0 ; i < divisors.length; i++) {
i === divisors.length - 1 ? output += `${divisors[i]}` : output += `${divisors[i]} + `
}
} else {
output = 'is NOT perfect.'
}
console.log(`${n}`, output)
}
이 문제는 완전수 여부를 따지는 문제로,
1부터 n의 제곱근까지만 확인하는 경우 1과 짝을 이루는 약수인 자기 자신은 divisors에 추가할 필요 없다.
위 풀이의 경우 if (i * i !== n && i !== 1)로 처리하였지만
sum = 1, divisors = [1]로 초기화 후 반복문의 범위를 2부터로 설정함으로써도 처리할 수 있다.
let input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map(Number)
let output = ''
for (const n of input) {
if (n === -1) break
let sum = 1, divisors = [1]
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
divisors.push(i)
sum += i
if (i * i !== n) {
divisors.push(n/i)
sum += n/i
}
}
}
divisors.sort((a, b) => a - b)
if (sum === n) {
output = '= '
for (let i = 0 ; i < divisors.length; i++) {
i === divisors.length - 1 ? output += `${divisors[i]}` : output += `${divisors[i]} + `
}
} else {
output = 'is NOT perfect.'
}
console.log(`${n}`, output)
}
약수를 구하는 방법 중 가장 일반적인 것은 1부터 N의 제곱근까지 확인하는 것으로,
바로 위의 풀이를 바탕으로 아래 내용까지 살펴보도록 하자.
참고) 백준 2501번
2. 배열의 합 구하기
반복문 이용
앞선 풀이들에서는 반복문을 이용하여 약수가 발견될 때마다 sum += i를 함으로써 약수들의 합을 구하였지만,
약수들을 divisors라는 배열에 저장해두었다는 사실을 활용하면 더 간단하게 약수들의 합을 구할 수 있다.
reduce 메소드 이용
let input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map(Number)
let output = ''
for (const n of input) {
if (n === -1) break
let sum = 0, divisors = [1]
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
divisors.push(i)
if (i * i !== n) {
divisors.push(n/i)
}
}
}
divisors.sort((a, b) => a - b)
sum = divisors.reduce((acc, cur) => acc += cur, 0)
if (sum === n) {
output = '= '
for (let i = 0 ; i < divisors.length; i++) {
i === divisors.length - 1 ? output += `${divisors[i]}` : output += `${divisors[i]} + `
}
} else {
output = 'is NOT perfect.'
}
console.log(`${n}`, output)
}
반복문 안의 sum += i를 삭제하고 sum = divisors.reduce((acc, cur) => acc += cur, 0)를 추가하였다.
참고) 백준 1546번
3. 배열 출력하기
반복문과 조건문 이용
앞선 풀이들에서는 반복문과 조건문을 이용하여 마지막 요소가 아닐 경우 요소와 덧셈을, 마지막 요소일 경우 요소만 출력하도록 하였지만,
약수들을 divisors라는 배열에 저장해두었다는 사실을 활용하면 더 간단하게 약수들의 합을 구할 수 있다.
join 메소드 이용
let input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map(Number)
let output = ''
for (const n of input) {
if (n === -1) break
let sum = 0, divisors = [1]
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
divisors.push(i)
if (i * i !== n) {
divisors.push(n/i)
}
}
}
divisors.sort((a, b) => a - b)
sum = divisors.reduce((acc, cur) => acc += cur, 0)
if (sum === n) {
output = `= ${divisors.join(' + ')}`
} else {
output = 'is NOT perfect.'
}
console.log(`${n}`, output)
}
join 메소드로 반복문과 조건문을 한 번에 대신하였다.
💫 이 문제를 통해 배운 것
• 배열의 합을 구해야 할 경우 reduce 메소드를 떠올리자.
• 배열의 요소들을 연결해서 출력해야 할 경우 join 메소드를 떠올리자.