๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[Javascript] ์ˆซ์ž ๋ธ”๋ก (12923)

๋ฌธ์ œ๋งํฌ

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ˆซ์ž ๋ธ”๋ก

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)
}