๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
Algorithm/์ธํ”„๋Ÿฐ(inflearn)

[ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ(JavaScript) ] 23 - ๋ด‰์šฐ๋ฆฌ

by YWTechIT 2021. 8. 17.
728x90

๐Ÿ“ 23 - ๋ด‰์šฐ๋ฆฌ

์ž์‹ ์˜ ์ƒํ•˜์ขŒ์šฐ ์ˆซ์ž๋ณด๋‹ค ํฐ ์ˆซ์ž์˜ ๊ฐœ์ˆ˜๋ฅผ ์ฐพ์œผ๋ฉด ๋˜๋Š”๋ฐ, ์ƒํ•˜์ขŒ์šฐ๋ฅผ ํŒ๋ณ„ํ•  ๋•Œ๋Š” dx, dy์™€ ๊ฐ™์ด ๋ฐฉํ–ฅ ๋ฒกํ„ฐ๋ฅผ ์„ค์ •ํ•ด์ฃผ๋ฉด ํ™•์ธํ•˜๊ธฐ ํŽธํ•˜๋‹ค. ๋‚˜๋Š” ์ด๋ ‡๊ฒŒ ํ’€์—ˆ๋‹ค.

 

  1. ์ƒ, ํ•˜, ์ขŒ, ์šฐ์˜ ์ขŒํ‘œ๋ฅผ ํ•˜๋‚˜์”ฉ ํƒ์ƒ‰ํ•˜๊ณ  ์ตœ๋Œ“๊ฐ’์„ ๊ฐฑ์‹ ํ•œ๋‹ค.
  2. max๋กœ ๊ฐฑ์‹ ๋œ ์ฃผ๋ณ€ ์ขŒํ‘œ์™€ ์›๋ž˜ ๋‚˜์˜ ์ขŒํ‘œ์™€ ๋น„๊ตํ•œ๋‹ค์Œ ์›๋ž˜ ๋‚˜์˜ ์ขŒํ‘œ๊ฐ€ ๋” ํฌ๋ฉด cnt++ ํ•ด์ค€๋‹ค.

 

๊ฐ•์‚ฌ๋‹˜์€ ์ด๋ ‡๊ฒŒ ํ‘ธ์…จ๋‹ค.

  1. flag๋ฅผ ์„ค์ •ํ•œ๋‹ค.
  2. ์›๋ž˜ ๋‚˜์˜ ์ขŒํ‘œ๋ณด๋‹ค ์ฃผ๋ณ€์ขŒํ‘œ๊ฐ€ ํฌ๋ฉด flag๋ฅผ 0์œผ๋กœ ๋ฐ”๊พผ๋‹ค.
  3. ์ฃผ๋ณ€ ์ขŒํ‘œ์˜ ํƒ์ƒ‰์ด ๋๋‚ฌ๋Š”๋ฐ๋„ flag๊ฐ€ 1์ด๋ฉด ์›๋ž˜ ๋‚˜์˜ ์ขŒํ‘œ๊ฐ€ ํฐ ๊ฒƒ์ด๋ฏ€๋กœ cnt++ ํ•ด์ค€๋‹ค.

 

let n = 5;
let arr = [[5, 3, 7, 2, 3], [3, 7, 1, 6, 1], [7, 2, 5, 3, 4], [4, 3, 6, 4, 1], [8, 7, 3, 5, 2]];

console.log(solution(n, arr));

// ๋‚˜์˜ ์ฝ”๋“œ
function solution(n, arr){
    let cnt = 0;
    let dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1];

    for (let x=0; x<n; x++){
        for(let y=0; y<n; y++){
            let surround = 0;
            for (let i=0; i<4; i++){
                let nx = x + dx[i];
                let ny = y + dy[i];

                if (nx<0 || ny<0 || nx>=n || ny>=n) continue
                if (surround < arr[nx][ny]) surround = arr[nx][ny]
            }
            if (arr[x][y] > surround) cnt++;
        }
    }
    return cnt;
}

 

let n = 5;
let arr = [[5, 3, 7, 2, 3], [3, 7, 1, 6, 1], [7, 2, 5, 3, 4], [4, 3, 6, 4, 1], [8, 7, 3, 5, 2]];

console.log(solution(n, arr));

// ๊ฐ•์˜ ์ฝ”๋“œ
function solution(n, arr){
    let cnt = 0;
    let dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1];

    for (let x=0; x<n; x++){
        for(let y=0; y<n; y++){
            let flag = 1;
            for (let i=0; i<4; i++){
                let nx = x + dx[i];
                let ny = y + dy[i];

                if (nx<0 || ny<0 || nx>=n || ny>=n) continue
                if (arr[nx][ny] > arr[x][y]){
                    flag = 0;
                    break;
                }
            }
            if (flag) cnt ++;
        }
    }
    return cnt;
}
๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€