๐ŸŽˆ[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํ–‰๋ ฌ ํ…Œ๋‘๋ฆฌ ํšŒ์ „ํ•˜๊ธฐ

Chobbyยท2022๋…„ 1์›” 23์ผ
0

Programmers

๋ชฉ๋ก ๋ณด๊ธฐ
2/345

rows x columns ํฌ๊ธฐ์ธ ํ–‰๋ ฌ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ํ–‰๋ ฌ์—๋Š” 1๋ถ€ํ„ฐ rows x columns๊นŒ์ง€์˜ ์ˆซ์ž๊ฐ€ ํ•œ ์ค„์”ฉ ์ˆœ์„œ๋Œ€๋กœ ์ ํ˜€์žˆ์Šต๋‹ˆ๋‹ค. ์ด ํ–‰๋ ฌ์—์„œ ์ง์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ๋ฒ”์œ„๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ์„ ํƒํ•ด, ํ…Œ๋‘๋ฆฌ ๋ถ€๋ถ„์— ์žˆ๋Š” ์ˆซ์ž๋“ค์„ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „์‹œํ‚ค๋ ค ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ ํšŒ์ „์€ (x1, y1, x2, y2)์ธ ์ •์ˆ˜ 4๊ฐœ๋กœ ํ‘œํ˜„ํ•˜๋ฉฐ, ๊ทธ ์˜๋ฏธ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

x1 ํ–‰ y1 ์—ด๋ถ€ํ„ฐ x2 ํ–‰ y2 ์—ด๊นŒ์ง€์˜ ์˜์—ญ์— ํ•ด๋‹นํ•˜๋Š” ์ง์‚ฌ๊ฐํ˜•์—์„œ ํ…Œ๋‘๋ฆฌ์— ์žˆ๋Š” ์ˆซ์ž๋“ค์„ ํ•œ ์นธ์”ฉ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•ฉ๋‹ˆ๋‹ค.
๋‹ค์Œ์€ 6 x 6 ํฌ๊ธฐ ํ–‰๋ ฌ์˜ ์˜ˆ์‹œ์ž…๋‹ˆ๋‹ค.

์ด ํ–‰๋ ฌ์— (2, 2, 5, 4) ํšŒ์ „์„ ์ ์šฉํ•˜๋ฉด, ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด 2ํ–‰ 2์—ด๋ถ€ํ„ฐ 5ํ–‰ 4์—ด๊นŒ์ง€ ์˜์—ญ์˜ ํ…Œ๋‘๋ฆฌ๊ฐ€ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ์ค‘์•™์˜ 15์™€ 21์ด ์žˆ๋Š” ์˜์—ญ์€ ํšŒ์ „ํ•˜์ง€ ์•Š๋Š” ๊ฒƒ์„ ์ฃผ์˜ํ•˜์„ธ์š”.

ํ–‰๋ ฌ์˜ ์„ธ๋กœ ๊ธธ์ด(ํ–‰ ๊ฐœ์ˆ˜) rows, ๊ฐ€๋กœ ๊ธธ์ด(์—ด ๊ฐœ์ˆ˜) columns, ๊ทธ๋ฆฌ๊ณ  ํšŒ์ „๋“ค์˜ ๋ชฉ๋ก queries๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ๊ฐ ํšŒ์ „๋“ค์„ ๋ฐฐ์—ด์— ์ ์šฉํ•œ ๋’ค, ๊ทธ ํšŒ์ „์— ์˜ํ•ด ์œ„์น˜๊ฐ€ ๋ฐ”๋€ ์ˆซ์ž๋“ค ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ์ˆซ์ž๋“ค์„ ์ˆœ์„œ๋Œ€๋กœ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ
rows๋Š” 2 ์ด์ƒ 100 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
columns๋Š” 2 ์ด์ƒ 100 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
์ฒ˜์Œ์— ํ–‰๋ ฌ์—๋Š” ๊ฐ€๋กœ ๋ฐฉํ–ฅ์œผ๋กœ ์ˆซ์ž๊ฐ€ 1๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ์ฆ๊ฐ€ํ•˜๋ฉด์„œ ์ ํ˜€์žˆ์Šต๋‹ˆ๋‹ค.
์ฆ‰, ์•„๋ฌด ํšŒ์ „๋„ ํ•˜์ง€ ์•Š์•˜์„ ๋•Œ, i ํ–‰ j ์—ด์— ์žˆ๋Š” ์ˆซ์ž๋Š” ((i-1) x columns + j)์ž…๋‹ˆ๋‹ค.
queries์˜ ํ–‰์˜ ๊ฐœ์ˆ˜(ํšŒ์ „์˜ ๊ฐœ์ˆ˜)๋Š” 1 ์ด์ƒ 10,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
queries์˜ ๊ฐ ํ–‰์€ 4๊ฐœ์˜ ์ •์ˆ˜ [x1, y1, x2, y2]์ž…๋‹ˆ๋‹ค.
x1 ํ–‰ y1 ์—ด๋ถ€ํ„ฐ x2 ํ–‰ y2 ์—ด๊นŒ์ง€ ์˜์—ญ์˜ ํ…Œ๋‘๋ฆฌ๋ฅผ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•œ๋‹ค๋Š” ๋œป์ž…๋‹ˆ๋‹ค.
1 โ‰ค x1 < x2 โ‰ค rows, 1 โ‰ค y1 < y2 โ‰ค columns์ž…๋‹ˆ๋‹ค.
๋ชจ๋“  ํšŒ์ „์€ ์ˆœ์„œ๋Œ€๋กœ ์ด๋ฃจ์–ด์ง‘๋‹ˆ๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด, ๋‘ ๋ฒˆ์งธ ํšŒ์ „์— ๋Œ€ํ•œ ๋‹ต์€ ์ฒซ ๋ฒˆ์งธ ํšŒ์ „์„ ์‹คํ–‰ํ•œ ๋‹ค์Œ, ๊ทธ ์ƒํƒœ์—์„œ ๋‘ ๋ฒˆ์งธ ํšŒ์ „์„ ์‹คํ–‰ํ–ˆ์„ ๋•Œ ์ด๋™ํ•œ ์ˆซ์ž ์ค‘ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

function solution(rows, columns, queries) {
    const result = []
    // ๋ฐฐ์—ด ์ƒ์„ฑ
    let arr = []
    let lastNum = 1
    for(let i = 1 ; i <= rows; i++) {
        let rowArr = []
        for(let j = 1 ; j <= columns ; j ++) {
            rowArr.push(lastNum)
            lastNum++
        }
        arr.push(rowArr)
    }
    // ์ฟผ๋ฆฌ ์ „์ฒด ๊ฐœ์ˆ˜๋งŒํผ ๋ฐ˜๋ณต
    for(let i = 0 ; i < queries.length ; i ++) {
        const start = queries[i].slice(0,2)
        const end = queries[i].slice(2,4)
        const box = []
        let temp = 0
        // ์ƒ๋‹จ ํšŒ์ „ x์ถ•
        for(let j = start[1] ; j <= end[1] ; j ++) {
            // ์ €์žฅ๊ณต๊ฐ„ ์ƒ์„ฑ
            temp = arr[start[0]-1][j-1]
            box.length ? arr[start[0]-1][j-1] = box[box.length-1] : null
            box.push(temp)
        }
        // ์šฐ์ธก ํšŒ์ „ y์ถ•
        for(let j = start[0]+1 ; j <= end[0] ; j++) {
            temp = arr[j-1][end[1]-1] 
            box.length ? arr[j-1][end[1]-1] = box[box.length-1] : null
            box.push(temp)
        }
        // ํ•˜๋‹จ ํšŒ์ „ x์ถ•
        for(let j = end[1]-1 ; j >= start[1] ; j --) {
            temp = arr[end[0]-1][j-1]
            box.length ? arr[end[0]-1][j-1] = box[box.length-1] : null
            box.push(temp)
        }
        // ์ขŒ์ธก ํšŒ์ „ y์ถ•
        for(let j = end[0]-1 ; j >= start[0] ; j --) {
            temp = arr[j-1][start[1]-1]
            box.length ? arr[j-1][start[1]-1] = box[box.length-1] : null
            box.push(temp)
        }
        result.push(Math.min(...box))
    }
    return result
}

์ƒ ์šฐ ํ•˜ ์ขŒ ์ˆœ์œผ๋กœ ๋Œ์•„๊ฐ€๋ฉฐ ํšŒ์ „์„ ๋ฐฐ์—ด์— ๋ฐ˜์˜ํ•˜์˜€์Œ

์ฝ์–ด์ฃผ์…”์„œ ๊ฐ์‚ฌํ•ฉ๋‹ˆ๋‹ค ^^

profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

0๊ฐœ์˜ ๋Œ“๊ธ€