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

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

[Javascript] n^2 ๋ฐฐ์—ด ์ž๋ฅด๊ธฐ (87390)

 

๋ฌธ์ œ๋งํฌ

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - n^2 ๋ฐฐ์—ด ์ž๋ฅด๊ธฐ

์ •์ˆ˜ n, left, right๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๋‹ค์Œ ๊ณผ์ •์„ ๊ฑฐ์ณ์„œ 1์ฐจ์› ๋ฐฐ์—ด์„ ๋งŒ๋“ค๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค. nํ–‰ n์—ด ํฌ๊ธฐ์˜ ๋น„์–ด์žˆ๋Š” 2์ฐจ์› ๋ฐฐ์—ด์„ ๋งŒ๋“ญ๋‹ˆ๋‹ค. i = 1, 2, 3, ..., n์— ๋Œ€ํ•ด์„œ, ๋‹ค์Œ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค. 1ํ–‰ 1์—ด๋ถ€

programmers.co.kr

 

์ ‘๊ทผ ๋ฐฉ๋ฒ•

์ฒ˜์Œ์—๋Š” ๋ฌธ์ œ์—์„œ ์นœ์ ˆํ•˜๊ฒŒ ๊ฐ€์•ผํ•˜๋Š” ๋ฐฉํ–ฅ์„ ํ•˜๋‚˜์”ฉ ์•Œ๋ ค์ฃผ์–ด์„œ
์ˆœ์ง„ํ•˜๊ฒŒ ๋”ฐ๋ผ ํ’€์—ˆ๋‹ค..

ํ•˜์ง€๋งŒ 1 <= n <= 10^7 ์ด๋ผ๋Š” ๋ฒ”์œ„์ด๊ธฐ ๋•Œ๋ฌธ์—
2์ฐจ์› ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ๊ฐ’์„ ์ฑ„์šด O(n^2)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” ํ†ต๊ณผํ•  ์ˆ˜ ์—†์—ˆ๋‹ค.

๋•Œ๋ฌธ์— left์™€ right๊ฐ€ 2์ฐจ์› ํ–‰๋ ฌ์—์„œ ์–ด๋–ค ์œ„์น˜์— ์žˆ๋Š”์ง€ ํŒจํ„ด์„ ์ฐพ์•„์•ผ ํ•œ๋‹ค.

n = 3, left = 2, right = 5
1 2 3                                    
2 2 3                                 
3 3 3   => 1 2 3 2 2 3 3 3 3

n = 4, left = 7, right = 14 ์ผ๋•Œ
1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4 => 1 2 3 4 2 2 3 4 3 3 3 4 4 4 4 4

์ง์ ‘ ๊ทธ๋ ค๋ณด๋‹ˆ ํŒจํ„ด์ด ๋ˆˆ์— ๋ณด์ธ๋‹ค.

left    =>   left / n ํ–‰, left % n ์—ด
right  =>   right / n ํ–‰, right % n์—ด
์ฆ‰, ๋‘˜๋‹ค /n, %n์œผ๋กœ ์ขŒํ‘œ๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

2์ฐจ ํ–‰๋ ฌ์—์„œ ์ขŒํ‘œ์˜ ๊ฐ’์€ Math.max(x, y) + 1๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์œผ๋‹ˆ ์ด์ œ ๋‹ต์„ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

 

// ํŒจํ„ด์„ ์ฐพ์•„ ํ’€์ดํ•œ ์ฝ”๋“œ

function solution(n, left, right) {
    var answer = []
    
    while(left <= right){
        answer.push(Math.max(Math.floor(left / n) , left % n) + 1);
        left++;
    }
    
    return answer
}
// ํ–‰๋ ฌ์„ ๋งŒ๋“ค์–ด ํ‘ผ ์ฝ”๋“œ

function solution(n, left, right) {
    const arr = new Array(n).fill(0).map(() => Array(n))
    
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            arr[i][j] = Math.max(i, j) + 1;
        }
    }
    
    const arrConcat = arr.reduce((acc,cur) => {
      return acc.concat(cur);
    });
    
    return arrConcat.slice(left, right+1)
}