๋ฌธ์ ๋งํฌ
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์ซ์ ๋ธ๋ก
1 10 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5]
programmers.co.kr
์ ๊ทผ ๋ฐฉ๋ฒ
์ฒ์์ ๊ฐ๋จํ๊ฒ 2์ค for๋ฌธ์ ์ฌ์ฉํ์ฌ 1 ~ end๊น์ง์ result array๋ฅผ ๊ตฌํ์ฌ
begin๋ถํฐ end๊น์ง sliceํ์ฌ ๋ต์ ๊ตฌํ์๋ค.
๊ทธ๋ฐ๋ฐ ์ฃผ์ด์ง begin๊ณผ end์ ๋ฒ์๊ฐ 1 ~ 1์ฒ๋ง์ผ๋ก ๋์ ๋ฒ์๋ฅผ ๊ฐ์ง๊ณ ์์ด 2์ค for๋ฌธ์ผ๋ก ์ฌ์ฉํ๋ฉด O(n^2)์ผ๋ก์ด๋ ๊ฒ ๊ธด ์๊ฐ์ด ๊ฑธ๋ ธ๋ค.
๊ทธ๋์ ์ต๋ nlogn์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ๋๋ก ํ์ด๋ฅผ ๋ค์ ์๊ฐํ์๋ค.
๊ณ ์น ์ 1. 1๋ถํฐ end๊น์ง ๋ชจ๋ ๊ตฌํ๋๊ฒ ๋๋ฌด ๋นํจ์จ์ ์ธ๊ฑฐ ๊ฐ๋ค๊ณ ์น ์ 2. ๋ฌธ์ ๋ฅผ ๋ค์ ๋ณด๋ฉด ์ฝ์๊ฐ ์กด์ฌํ๋ค๋ฉด ์ฝ์์ ์ต๋ ๊ฐ์ ๊ฐ๊ณ , ์ฝ์๊ฐ ์กด์ฌํ์ง ์์ผ๋ฉด 1์ ๊ฐ๋๋ค๋ ๊ท์น์ด ์๋ค.
์ด๋ฅผ ํ์ฉํ์ฌ begin๋ถํฐ end๊น์ง ์์์ด๋ฉด 1, ์์๊ฐ ์๋๋ฉด ์ต๋ ์ฝ์๋ฅผ ๊ฐ๋๋ก ํ์ด๋ฅผ ์งํํ์๋ค.๊ทธ ๊ฒฐ๊ณผ ์ ํ์ฑ ํ ์คํธ์์ ์๊ฐ๋ณต์ก๋ ํจ์จ์ ๋งค์ฐ ์ฆ๊ฐํ๋๋ฐ, ์ฌ์ ํ ํจ์จ์ฑ ํ ์คํธ์์ ํ๋ฝํ์๋ค.
์ต๋ ์ฝ์๋ฅผ ๋ ํจ์จ์ ์ผ๋ก ๊ตฌํ๋ ๋ฐฉ๋ฒ์ด ์๋?
begin๋ถํฐ end๋ฒ์ ๋ด์ ์์์ผ๋ 1์ ๋ฃ๋ ๊ฒ ๊น์ง๋ ํจ์จ์ฑ์ ๋ฌธ์ ๊ฐ ์์ด๋ณด์ด์ง ์์๋ค.
์์๊ฐ ์๋ ๋ ์ต๋ ์ฝ์๋ฅผ ๊ตฌํ๋ ๋ฐฉ์์ ๊ณ ์ณ์ผํ ๊ฒ ๊ฐ์๋ฐ
๋ฐฉ๋ฒ์ด ์ ์๊ฐ์ด ์๋์ ๋ค๋ฅธ ๋ถ์ ์ฝ๋๋ฅผ ์ฐธ๊ณ ํ์๋ค.
const getDivisor = (num) => { for(let i = 2; i <= Math.sqrt(num); i++) { if(num % i === 0 && num / i <= 1e7) { return num / i; } } return 1; }โ
์์๋๋ก ๋ด๊ฐ ๊ตฌํ๋ ์์ ํ๋จ ํจ์์ ์ต๋ ์ฝ์๋ฅผ ๊ตฌํ๋ ํจ์๋ฅผ ํ๋๋ก ํฉ์ณ ๊ตฌํํ์ จ๋ค.
begin๊ณผ end์ ๋ฒ์๊ฐ 1 ~ 1,000,000,000 ์ด์ง๋ง ๋ธ๋ก์ ์๋ ์ต๋ 10,000,000๊ฐ์ด๋ฏ๋ก
๋งค๊ฐ๋ณ์ num(begin)์ด i๋ก ๋๋ ๊ฐ (๋ธ๋ก์ ๋ฃ์ ๊ฐ)์ด 10,000,000๋ณด๋ค ํฌ๋ค๋ฉด 1์ returnํ๋๋ก ํด์ผ ํจ์จ์ฑ ํ ์คํธ๋ฅผ ํต๊ณผํ ์ ์๋ค.
function solution(begin, end) {
const resultArr = new Array((end - begin)+1).fill(0);
let resultIdx = 0;
while(begin <= end){
if (begin === 1) {
resultArr[resultIdx] = 0;
resultIdx++;
begin++;
// console.log("1์ผ๋", resultArr, "begin", begin);
}
// ์์์ผ๋, ์๋๋ ์ฒ๋ฆฌ
getDivisor(begin) === 1 ? resultArr[resultIdx] = 1 : resultArr[resultIdx] = getDivisor(begin)
resultIdx++;
begin++;
}
return resultArr
}
const getDivisor = (num) => {
for(let i = 2; i <= Math.sqrt(num); i++) {
if(num % i === 0 && num / i <= 1e7) {
return num / i;
}
}
return 1;
}
// ์๊ฐ๋ณต์ก๋ ํจ์จ์ฑ ์ฆ๊ฐ, ์ฌ์ ํ ํจ์จ์ฑ ํ
์คํธ ํ๋ฝ
// ์ฃผ์ด์ง ๋ฒ์(begin, end) ๋ด์ ์กฐ๊ฑด์ ๋ง๋(์์์ผ๋ 1, ์๋๋ ์ต๋ ์ฝ์) ๊ฒฝ์ฐ๋ง resultArr์ ๋ฃ๋ ๊ฒฝ์ฐ
function solution(begin, end) {
const resultArr = new Array((end - begin)+1).fill(0);
let resultIdx = 0;
while(begin <= end){
if (begin === 1) {
resultArr[resultIdx] = 0;
resultIdx++;
begin++;
// console.log("1์ผ๋", resultArr, "begin", begin);
}
isPrime(begin) ? resultArr[resultIdx] = 1 : resultArr[resultIdx] = findMaxDivided(begin);
resultIdx++;
begin++;
}
return resultArr
}
const findMaxDivided = (num) => {
let max = 0;
for(let i = 2; i <= Math.floor(num / 2); i++){
if(num % i === 0) max = Math.max(max, i);
}
return max;
}
const isPrime = (num) => {
for(let i = 2; i <= Math.sqrt(num); i++){
if(num % i === 0) return false;
}
return num >= 2;
}
// ์ ํ์ฑ, ํจ์จ์ฑ ๋ชจ๋ ํ๋ฝํ ์ฝ๋
// 1~end๊น์ง ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ๊ตฌํ๊ณ ์ํ๋ ๋ถ๋ถ(begin, end)๋ง ์ถ์ถํ ์ฝ๋
function solution(begin, end) {
const resultArr = new Array(end).fill(0);
for(let i = 1; i <= Math.floor(end / 2); i++){
for(let j = 0; j <= end; j++){
if(j % i === 0 && i !== j){
resultArr[j] = i
}
}
}
return resultArr.slice(begin, end+1)
}
'์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Javascript] ๋ค์ ํฐ ์ซ์ (12911) (0) | 2022.06.18 |
---|---|
[Javascript] ์คํฌํธ๋ฆฌ (49993) (0) | 2022.06.18 |
[Javascript] ํฐ ์ ๋ง๋ค๊ธฐ (42883) (0) | 2022.06.12 |
[Javascript] ๊ตฌ๋ช ๋ณดํธ (42885) (0) | 2022.06.11 |
[Javascript] ์์ ์ฐพ๊ธฐ (42839) (0) | 2022.06.11 |