Logo
Hyunsu Blog
algorithm-simulation

๐Ÿ“†Published :Feb 17, 2024 โ€ข

๐Ÿ“†Updated :Feb 17, 2024 โ€ข

โ˜•๏ธ4min

์‹œ๋ฎฌ๋ ˆ์ด์…˜

์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฌธ์ œ๋Š” ์ฃผ์–ด์ง„ ์ƒํ™ฉ์„ ์™„๋ฒฝํ•˜๊ฒŒ ์ดํ•ด ํ•˜๊ณ  ์ด๋ฅผ ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ ํ•˜๋Š” ๊ณผ์ •์œผ๋กœ ๊ตฌํ˜„์— ์ค‘์ ์ด ๋งž์ถฐ์ ธ ์žˆ๋‹ค.

๊ทธ๋ž˜์„œ ๋ฐ”๋กœ ๋ฌธ์ œํ’€์ด๋กœ ๋„˜์–ด๊ฐ€๋ณผ๊นŒ ํ•œ๋‹ค.

์ด์ง„ ๋ณ€ํ™˜ ๋ฐ˜๋ณตํ•˜๊ธฐ ์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋ฌธ์ œ ์„ค๋ช… 0๊ณผ 1๋กœ ์ด๋ฃจ์–ด์ง„ ์–ด๋–ค ๋ฌธ์ž์—ด x์— ๋Œ€ํ•œ ์ด์ง„ ๋ณ€ํ™˜์„ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•ฉ๋‹ˆ๋‹ค. x์˜ ๋ชจ๋“  0์„ ์ œ๊ฑฐํ•ฉ๋‹ˆ๋‹ค. x์˜ ๊ธธ์ด๋ฅผ c๋ผ๊ณ  ํ•˜๋ฉด, x๋ฅผ "c๋ฅผ 2์ง„๋ฒ•์œผ๋กœ ํ‘œํ˜„ํ•œ ๋ฌธ์ž์—ด"๋กœ ๋ฐ”๊ฟ‰๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, x = "0111010"์ด๋ผ๋ฉด, x์— ์ด์ง„ ๋ณ€ํ™˜์„ ๊ฐ€ํ•˜๋ฉด x = "0111010" -> "1111" -> "100" ์ด ๋ฉ๋‹ˆ๋‹ค. 0๊ณผ 1๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด s๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. s๊ฐ€ "1"์ด ๋  ๋•Œ๊นŒ์ง€ ๊ณ„์†ํ•ด์„œ s์— ์ด์ง„ ๋ณ€ํ™˜์„ ๊ฐ€ํ–ˆ์„ ๋•Œ, ์ด์ง„ ๋ณ€ํ™˜์˜ ํšŸ์ˆ˜์™€ ๋ณ€ํ™˜ ๊ณผ์ •์—์„œ ์ œ๊ฑฐ๋œ ๋ชจ๋“  0์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ฐ๊ฐ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

function solution(s) { let cnt = 0 let zeroCnt = 0 while (s !== '1') { const zeroArr = s.match(/0/g) if (zeroArr && zeroArr.length > 0) { zeroCnt += zeroArr.length } s = s.replaceAll('0', '') const target = s.length s = target.toString(2) cnt += 1 } return [cnt, zeroCnt] }

์ด ์ฝ”๋“œ๋ฅผ ๋ฆฌํŒฉํ† ๋ง ํ•˜๋ฉด ์ด๋ ‡๊ฒŒ๋„ ๊ฐ€๋Šฅํ•˜๋‹ค.

function solution(s) { function solution(s) { let cnt = 0 let zeroCnt = 0 while (s !== '1') { zeroCnt += (s.match(/0/g) || []).length s = s.replaceAll('0', '').length.toString(2) cnt += 1 } return [cnt, zeroCnt] } }

์นดํŽซ ์ถœ์ฒ˜ : ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋ฌธ์ œ์„ค๋ช… Leo๋Š” ์นดํŽซ์„ ์‚ฌ๋Ÿฌ ๊ฐ”๋‹ค๊ฐ€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ค‘์•™์—๋Š” ๋…ธ๋ž€์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๊ณ  ํ…Œ๋‘๋ฆฌ 1์ค„์€ ๊ฐˆ์ƒ‰์œผ๋กœ ์น ํ•ด์ ธ ์žˆ๋Š” ๊ฒฉ์ž ๋ชจ์–‘ ์นดํŽซ์„ ๋ดค์Šต๋‹ˆ๋‹ค.

alt text

Leo๋Š” ์ง‘์œผ๋กœ ๋Œ์•„์™€์„œ ์•„๊นŒ ๋ณธ ์นดํŽซ์˜ ๋…ธ๋ž€์ƒ‰๊ณผ ๊ฐˆ์ƒ‰์œผ๋กœ ์ƒ‰์น ๋œ ๊ฒฉ์ž์˜ ๊ฐœ์ˆ˜๋Š” ๊ธฐ์–ตํ–ˆ์ง€๋งŒ, ์ „์ฒด ์นดํŽซ์˜ ํฌ๊ธฐ๋Š” ๊ธฐ์–ตํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. Leo๊ฐ€ ๋ณธ ์นดํŽซ์—์„œ ๊ฐˆ์ƒ‰ ๊ฒฉ์ž์˜ ์ˆ˜ brown, ๋…ธ๋ž€์ƒ‰ ๊ฒฉ์ž์˜ ์ˆ˜ yellow๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ ์นดํŽซ์˜ ๊ฐ€๋กœ, ์„ธ๋กœ ํฌ๊ธฐ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ด ๋ฌธ์ œ๋Š” ์ฃผ์–ด์ง„ yellow๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ฐ€๋กœ์˜ ๊ธธ์ด๋ฅผ ํ•˜๋‚˜์”ฉ ๋Š˜๋ ค๊ฐ€๋ฉด์„œ, yellow๋ฅผ ๋‘˜๋Ÿฌ์‹ธ๋Š” brown ๊ฒฉ์ž์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜์—ฌ ์ฃผ์–ด์ง„ brown๊ณผ ์ผ์น˜ํ•˜๋ฉด brown์˜ ๊ฐ€๋กœ, ์„ธ๋กœ ๊ฒฉ์ž๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค. yellow์˜ ๊ฐ€๋กœ ๊ธธ์ด๋ฅผ 1๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ๋Š˜๋ ค๊ฐ€๋ฉด์„œ ์กฐ๊ฑด์— ๋งž๋Š”์ง€ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์„ ํ†ตํ•ด ์™„์ „ ํƒ์ƒ‰์ž„์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

/** * * TimeComplexity: O(yellow/2) * @param {*} brown * @param {*} yellow * @returns */ function solution(brown, yellow) { let yellow_w = 0 let brown_w = 0 let brown_h = 0 // yellow๊ฐ€ 1์ด๋ฉด ๊ฐ€๋กœ, ์„ธ๋กœ ๊ธธ์ด๋Š” 3 (์ตœ์†Ÿ๊ฐ’) if (yellow === 1) { return [3, 3] } // yellow_h ๋ฅผ 1๋ถ€ํ„ฐ yellow/2๊นŒ์ง€ ๋ฐ˜๋ณต for (let yellow_h = 1; yellow_h <= yellow / 2; yellow_h++) { //yellow์˜ ๊ฐ€๋กœ๊ธธ์ด๊ฐ€ ์ •์ˆ˜์ธ์ง€ ํ™•์ธ if (yellow % yellow_h !== 0) continue //yellow์˜ ๊ฐ€๋กœ ๊ธธ์ด ๊ตฌํ•˜๊ธฐ yellow_w = Math.floor(yellow / yellow_h) // yellow์˜ ๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ ์„ธ๋กœ ๊ธธ์ด๋ณด๋‹ค ์ž‘์œผ๋ฉด continue if (yellow_h > yellow_w) continue // brown์˜ ๊ฐ€๋กœ, ์„ธ๋กœ ๊ธธ์ด ๊ตฌํ•˜๊ธฐ brown_w = yellow_w + 2 brown_h = yellow_h + 2 // brown์˜ ๊ฐ€๋กœ, ์„ธ๋กœ ๊ธธ์ด๊ฐ€ ๋งž์œผ๋ฉด break if (brown_w * 2 + brown_h * 2 - 4 === brown) break yellow_w += 1 } return [brown_w, brown_h] }

๋กค ์ผ€์ดํฌ ์ž๋ฅด๊ธฐ ์ถœ์ฒ˜ : ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋ฌธ์ œ ์š”์ 

๋ฌธ์ œ ์„ค๋ช… ์ฒ ์ˆ˜๋Š” ๋กค์ผ€์ดํฌ๋ฅผ ๋‘ ์กฐ๊ฐ์œผ๋กœ ์ž˜๋ผ์„œ ๋™์ƒ๊ณผ ํ•œ ์กฐ๊ฐ์”ฉ ๋‚˜๋ˆ  ๋จน์œผ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ด ๋กค์ผ€์ดํฌ์—๋Š” ์—ฌ๋Ÿฌ๊ฐ€์ง€ ํ† ํ•‘๋“ค์ด ์ผ๋ ฌ๋กœ ์˜ฌ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ์ฒ ์ˆ˜์™€ ๋™์ƒ์€ ๋กค์ผ€์ดํฌ๋ฅผ ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆ ๋จน์œผ๋ ค ํ•˜๋Š”๋ฐ, ๊ทธ๋“ค์€ ๋กค์ผ€์ดํฌ์˜ ํฌ๊ธฐ๋ณด๋‹ค ๋กค์ผ€์ดํฌ ์œ„์— ์˜ฌ๋ ค์ง„ ํ† ํ•‘๋“ค์˜ ์ข…๋ฅ˜์— ๋” ๊ด€์‹ฌ์ด ๋งŽ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ์ž˜๋ฆฐ ์กฐ๊ฐ๋“ค์˜ ํฌ๊ธฐ์™€ ์˜ฌ๋ ค์ง„ ํ† ํ•‘์˜ ๊ฐœ์ˆ˜์— ์ƒ๊ด€์—†์ด ๊ฐ ์กฐ๊ฐ์— ๋™์ผํ•œ ๊ฐ€์ง“์ˆ˜์˜ ํ† ํ•‘์ด ์˜ฌ๋ผ๊ฐ€๋ฉด ๊ณตํ‰ํ•˜๊ฒŒ ๋กค์ผ€์ดํฌ๊ฐ€ ๋‚˜๋ˆ„์–ด์ง„ ๊ฒƒ์œผ๋กœ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ๋กค์ผ€์ดํฌ์— 4๊ฐ€์ง€ ์ข…๋ฅ˜์˜ ํ† ํ•‘์ด ์˜ฌ๋ ค์ ธ ์žˆ๋‹ค๊ณ  ํ•ฉ์‹œ๋‹ค. ํ† ํ•‘๋“ค์„ 1, 2, 3, 4์™€ ๊ฐ™์ด ๋ฒˆํ˜ธ๋กœ ํ‘œ์‹œํ–ˆ์„ ๋•Œ, ์ผ€์ดํฌ ์œ„์— ํ† ํ•‘๋“ค์ด [1, 2, 1, 3, 1, 4, 1, 2] ์ˆœ์„œ๋กœ ์˜ฌ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์„ธ ๋ฒˆ์งธ ํ† ํ•‘(1)๊ณผ ๋„ค ๋ฒˆ์งธ ํ† ํ•‘(3) ์‚ฌ์ด๋ฅผ ์ž๋ฅด๋ฉด ๋กค์ผ€์ดํฌ์˜ ํ† ํ•‘์€ [1, 2, 1], [3, 1, 4, 1, 2]๋กœ ๋‚˜๋‰˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ฒ ์ˆ˜๊ฐ€ [1, 2, 1]์ด ๋†“์ธ ์กฐ๊ฐ์„, ๋™์ƒ์ด [3, 1, 4, 1, 2]๊ฐ€ ๋†“์ธ ์กฐ๊ฐ์„ ๋จน๊ฒŒ ๋˜๋ฉด ์ฒ ์ˆ˜๋Š” ๋‘ ๊ฐ€์ง€ ํ† ํ•‘(1, 2)์„ ๋ง›๋ณผ ์ˆ˜ ์žˆ์ง€๋งŒ, ๋™์ƒ์€ ๋„ค ๊ฐ€์ง€ ํ† ํ•‘(1, 2, 3, 4)์„ ๋ง›๋ณผ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ์ด๋Š” ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆ„์–ด์ง„ ๊ฒƒ์ด ์•„๋‹™๋‹ˆ๋‹ค. ๋งŒ์•ฝ ๋กค์ผ€์ดํฌ์˜ ๋„ค ๋ฒˆ์งธ ํ† ํ•‘(3)๊ณผ ๋‹ค์„ฏ ๋ฒˆ์งธ ํ† ํ•‘(1) ์‚ฌ์ด๋ฅผ ์ž๋ฅด๋ฉด [1, 2, 1, 3], [1, 4, 1, 2]๋กœ ๋‚˜๋‰˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ด ๊ฒฝ์šฐ ์ฒ ์ˆ˜๋Š” ์„ธ ๊ฐ€์ง€ ํ† ํ•‘(1, 2, 3)์„, ๋™์ƒ๋„ ์„ธ ๊ฐ€์ง€ ํ† ํ•‘(1, 2, 4)์„ ๋ง›๋ณผ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ์ด๋Š” ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆ„์–ด์ง„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๊ณตํ‰ํ•˜๊ฒŒ ๋กค์ผ€์ดํฌ๋ฅผ ์ž๋ฅด๋Š” ๋ฐฉ๋ฒ•์€ ์—ฌ๋Ÿฌ๊ฐ€์ง€ ์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์œ„์˜ ๋กค์ผ€์ดํฌ๋ฅผ [1, 2, 1, 3, 1], [4, 1, 2]์œผ๋กœ ์ž˜๋ผ๋„ ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋‰ฉ๋‹ˆ๋‹ค. ์–ด๋–ค ๊ฒฝ์šฐ์—๋Š” ๋กค์ผ€์ดํฌ๋ฅผ ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆ„์ง€ ๋ชปํ•  ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค. ๋กค์ผ€์ดํฌ์— ์˜ฌ๋ ค์ง„ ํ† ํ•‘๋“ค์˜ ๋ฒˆํ˜ธ๋ฅผ ์ €์žฅํ•œ ์ •์ˆ˜ ๋ฐฐ์—ด topping์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋กค์ผ€์ดํฌ๋ฅผ ๊ณตํ‰ํ•˜๊ฒŒ ์ž๋ฅด๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ด ๋ฌธ์ œ๋Š” ๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ ํ† ํ•‘์˜ left์™€ right๋ฅผ ๋‚˜๋ˆ„์–ด ๊ทธ๋Œ€๋กœ ๊ตฌํ˜„ํ•˜์˜€๋‹ค. ๊ตฌํ˜„ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” Map์„ ์ด์šฉํ•˜์—ฌ left์™€ right์— ํ† ํ•‘์„ ๋„ฃ๊ณ  ๋นผ๋Š” ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•˜์˜€๋‹ค.

/** * * * Time Complexity : O(n) * @param {*} topping * @returns */ function solution(topping) { var answer = 0 let left = [] let right = [] const leftToppingMapper = new Map() const rightToppingMapper = new Map() // ์ดˆ๊ธฐ right์— ๋ชจ๋“  ํ† ํ•‘์„ ๋„ฃ๊ณ , ํ† ํ•‘์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ผ๋‹ค topping.forEach((v) => { rightToppingMapper.set(v, (rightToppingMapper.get(v) || 0) + 1) right.push(v) }) //์ฃผ์–ด์ง„ ํ† ํ•‘๋งŒํผ ์ˆœํšŒํ•˜๋ฉด์„œ right์—์„œ ํ•˜๋‚˜์”ฉ pop ํ•˜์—ฌ, left์— ๋„ฃ๋Š”๋‹ค. // ์ˆœํšŒ๋Š” right๊ฐ€ ๋นŒ๋•Œ๊นŒ์ง€ ํ•œ๋‹ค. while (right.length) { //left๋กœ ์˜ฎ๊ธฐ๊ธฐ const last = right.pop() left.push(last) //left์— ํ† ํ•‘์„ ์ถ”๊ฐ€ ํ•œ๋‹ค. leftToppingMapper.set(last, (leftToppingMapper.get(last) || 0) + 1) //right์—์„œ ํ† ํ•‘์„ ์ œ๊ฑฐํ•œ๋‹ค. rightToppingMapper.set(last, rightToppingMapper.get(last) - 1) //right์—์„œ ํ† ํ•‘์„ ์ œ๊ฑฐํ•  ๋•Œ, 0 ์ด ๋˜๋ฉด map์—์„œ ์ œ๊ฑฐํ•œ๋‹ค. if (rightToppingMapper.get(last) === 0) { rightToppingMapper.delete(last) } // map์— ์ €์žฅ๋œ key์˜ ๊ฐœ์ˆ˜๋กœ ๋น„๊ตํ•˜์—ฌ ๊ฐ™์œผ๋ฉด answer๋ฅผ ์ฆ๊ฐ€์‹œํ‚จ๋‹ค. if (leftToppingMapper.size === rightToppingMapper.size) { answer += 1 } } return answer }

์ ํ”„์™€ ์ˆœ๊ฐ„์ด๋™ ์ถœ์ฒ˜:ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋ฌธ์ œ ์„ค๋ช… OO ์—ฐ๊ตฌ์†Œ๋Š” ํ•œ ๋ฒˆ์— K ์นธ์„ ์•ž์œผ๋กœ ์ ํ”„ํ•˜๊ฑฐ๋‚˜, (ํ˜„์žฌ๊นŒ์ง€ ์˜จ ๊ฑฐ๋ฆฌ) x 2 ์— ํ•ด๋‹นํ•˜๋Š” ์œ„์น˜๋กœ ์ˆœ๊ฐ„์ด๋™์„ ํ•  ์ˆ˜ ์žˆ๋Š” ํŠน์ˆ˜ํ•œ ๊ธฐ๋Šฅ์„ ๊ฐ€์ง„ ์•„์ด์–ธ ์ŠˆํŠธ๋ฅผ ๊ฐœ๋ฐœํ•˜์—ฌ ํŒ๋งคํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์•„์ด์–ธ ์ŠˆํŠธ๋Š” ๊ฑด์ „์ง€๋กœ ์ž‘๋™๋˜๋Š”๋ฐ, ์ˆœ๊ฐ„์ด๋™์„ ํ•˜๋ฉด ๊ฑด์ „์ง€ ์‚ฌ์šฉ๋Ÿ‰์ด ์ค„์ง€ ์•Š์ง€๋งŒ, ์•ž์œผ๋กœ K ์นธ์„ ์ ํ”„ํ•˜๋ฉด K ๋งŒํผ์˜ ๊ฑด์ „์ง€ ์‚ฌ์šฉ๋Ÿ‰์ด ๋“ญ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ ์•„์ด์–ธ ์ŠˆํŠธ๋ฅผ ์ฐฉ์šฉํ•˜๊ณ  ์ด๋™ํ•  ๋•Œ๋Š” ์ˆœ๊ฐ„ ์ด๋™์„ ํ•˜๋Š” ๊ฒƒ์ด ๋” ํšจ์œจ์ ์ž…๋‹ˆ๋‹ค. ์•„์ด์–ธ ์ŠˆํŠธ ๊ตฌ๋งค์ž๋Š” ์•„์ด์–ธ ์ŠˆํŠธ๋ฅผ ์ฐฉ์šฉํ•˜๊ณ  ๊ฑฐ๋ฆฌ๊ฐ€ N ๋งŒํผ ๋–จ์–ด์ ธ ์žˆ๋Š” ์žฅ์†Œ๋กœ ๊ฐ€๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋‹จ, ๊ฑด์ „์ง€ ์‚ฌ์šฉ๋Ÿ‰์„ ์ค„์ด๊ธฐ ์œ„ํ•ด ์ ํ”„๋กœ ์ด๋™ํ•˜๋Š” ๊ฒƒ์€ ์ตœ์†Œ๋กœ ํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์•„์ด์–ธ ์ŠˆํŠธ ๊ตฌ๋งค์ž๊ฐ€ ์ด๋™ํ•˜๋ ค๋Š” ๊ฑฐ๋ฆฌ N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์‚ฌ์šฉํ•ด์•ผ ํ•˜๋Š” ๊ฑด์ „์ง€ ์‚ฌ์šฉ๋Ÿ‰์˜ ์ตœ์†Ÿ๊ฐ’์„ returnํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค์–ด ์ฃผ์„ธ์š”. ์˜ˆ๋ฅผ ๋“ค์–ด ๊ฑฐ๋ฆฌ๊ฐ€ 5๋งŒํผ ๋–จ์–ด์ ธ ์žˆ๋Š” ์žฅ์†Œ๋กœ ๊ฐ€๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์•„์ด์–ธ ์ŠˆํŠธ๋ฅผ ์ž…๊ณ  ๊ฑฐ๋ฆฌ๊ฐ€ 5๋งŒํผ ๋–จ์–ด์ ธ ์žˆ๋Š” ์žฅ์†Œ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋Š” ์—ฌ๋Ÿฌ ๊ฐ€์ง€์ž…๋‹ˆ๋‹ค. ์ฒ˜์Œ ์œ„์น˜ 0 ์—์„œ 5 ์นธ์„ ์•ž์œผ๋กœ ์ ํ”„ํ•˜๋ฉด ๋ฐ”๋กœ ๋„์ฐฉํ•˜์ง€๋งŒ, ๊ฑด์ „์ง€ ์‚ฌ์šฉ๋Ÿ‰์ด 5 ๋งŒํผ ๋“ญ๋‹ˆ๋‹ค. ์ฒ˜์Œ ์œ„์น˜ 0 ์—์„œ 2 ์นธ์„ ์•ž์œผ๋กœ ์ ํ”„ํ•œ ๋‹ค์Œ ์ˆœ๊ฐ„์ด๋™ ํ•˜๋ฉด (ํ˜„์žฌ๊นŒ์ง€ ์˜จ ๊ฑฐ๋ฆฌ : 2) x 2์— ํ•ด๋‹นํ•˜๋Š” ์œ„์น˜๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ์œ„์น˜ 4๋กœ ์ด๋™ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ 1 ์นธ์„ ์•ž์œผ๋กœ ์ ํ”„ํ•˜๋ฉด ๋„์ฐฉํ•˜๋ฏ€๋กœ ๊ฑด์ „์ง€ ์‚ฌ์šฉ๋Ÿ‰์ด 3 ๋งŒํผ ๋“ญ๋‹ˆ๋‹ค. ์ฒ˜์Œ ์œ„์น˜ 0 ์—์„œ 1 ์นธ์„ ์•ž์œผ๋กœ ์ ํ”„ํ•œ ๋‹ค์Œ ์ˆœ๊ฐ„์ด๋™ ํ•˜๋ฉด (ํ˜„์žฌ๊นŒ์ง€ ์˜จ ๊ฑฐ๋ฆฌ : 1) x 2์— ํ•ด๋‹นํ•˜๋Š” ์œ„์น˜๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ์œ„์น˜ 2๋กœ ์ด๋™๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ๋‹ค์‹œ ์ˆœ๊ฐ„์ด๋™ ํ•˜๋ฉด (ํ˜„์žฌ๊นŒ์ง€ ์˜จ ๊ฑฐ๋ฆฌ : 2) x 2 ๋งŒํผ ์ด๋™ํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ์œ„์น˜ 4๋กœ ์ด๋™ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ 1 ์นธ์„ ์•ž์œผ๋กœ ์ ํ”„ํ•˜๋ฉด ๋„์ฐฉํ•˜๋ฏ€๋กœ ๊ฑด์ „์ง€ ์‚ฌ์šฉ๋Ÿ‰์ด 2 ๋งŒํผ ๋“ญ๋‹ˆ๋‹ค. ์œ„์˜ 3๊ฐ€์ง€ ๊ฒฝ์šฐ ๊ฑฐ๋ฆฌ๊ฐ€ 5๋งŒํผ ๋–จ์–ด์ ธ ์žˆ๋Š” ์žฅ์†Œ๋กœ ๊ฐ€๊ธฐ ์œ„ํ•ด์„œ 3๋ฒˆ์งธ ๊ฒฝ์šฐ๊ฐ€ ๊ฑด์ „์ง€ ์‚ฌ์šฉ๋Ÿ‰์ด ๊ฐ€์žฅ ์ ์œผ๋ฏ€๋กœ ๋‹ต์€ 2๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ์ œํ•œ ์‚ฌํ•ญ ์ˆซ์ž N: 1 ์ด์ƒ 10์–ต ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ˆซ์ž K: 1 ์ด์ƒ์˜ ์ž์—ฐ์ˆ˜

์ด ๋ฌธ์ œ๋Š” ์ ํ”„ ํ•  ๋•Œ์™€ ์ˆœ๊ฐ„ ์ด๋™ ํ•  ๋•Œ์˜ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜์—์„œ ๋„์ฐฉ์ง€์ ๊นŒ์ง€์˜ ์ตœ์†Œ๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ์ ‘๊ทผํ•˜์˜€๋‹ค. ํ•˜์ง€๋งŒ N์ด 10 ์–ต์ด๋ฏ€๋กœ DFS๋กœ๋Š” ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚œ๋‹ค.

/** * * @param {*} n * @returns */ function solution(n) { let minVals = [] dfs(1, 1) function dfs(curVal, curLocation) { if (curLocation === n) { minVals.push(curVal) return } dfs(curVal + 1, curLocation + 1) //jump if (curLocation * 2 > n) { return } dfs(curVal, curLocation * 2) //์ˆœ๊ฐ„์ด๋™ } return Math.min(...minVals) }

๋ฌธ์ œ์˜ ๊ทœ์น™์„ ์ž˜ ํ™œ์šฉํ•˜๋Š” ๊ฒƒ์ด ์ด ๋ฌธ์ œ์˜ ํ•ต์‹ฌ์ด๋‹ค.

์ˆœ๊ฐ„์ด๋™์˜ ๊ฒฝ์šฐ ํ˜„์žฌ ์œ„์น˜์—์„œ ๋‹ค์Œ์œ„์น˜๋Š” 2๋ฐฐ์ด๋‹ค. ์ฆ‰ ๋„์ฐฉ์ง€์ (N)์ด ์ง์ˆ˜์ด๋ฉด ์ˆœ๊ฐ„์ด๋™์„ ํ–ˆ๋‹ค๋Š” ์˜๋ฏธ์ด๋ฏ€๋กœ N/2๋กœ ์ด๋™ํ•œ๋‹ค. ์ด ๋•Œ ๋ฐฐํ„ฐ๋ฆฌ ์†Œ๋น„๋Š” ์—†๋‹ค.

๋„์ฐฉ์ง€์ ์ด ํ™€์ˆ˜์ธ ๊ฒฝ์šฐ๋Š” ์ ํ”„๋ฅผ ํ–ˆ๋‹ค๊ณ  ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

๊ทธ๋Ÿผ ๋„์ฐฉ์ง€์ ์„ 2๋กœ ๋‚˜๋ˆ„์–ด 0์œผ๋กœ ๋–จ์–ด์ง€๋ฉด ๋ฐฐํ„ฐ๋ฆฌ ์†Œ๋น„๋Š” ์—†์œผ๋ฉฐ, 2๋กœ ๋‚˜๋ˆ„์–ด ๋‚˜๋จธ์ง€๊ฐ€ 1์ด ๋˜๋ฉด ์ ํ”„๋ฅผ ํ•œ ๋ฒˆ ํ–ˆ๋‹ค๊ณ  ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

์ด์ง„์ˆ˜๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ๊ณผ์ •๊ณผ ๊ฐ™๋‹ค.

function solution(n) { return Array.from(n.toString(2)).filter((v) => v === '1').length }

์บ๋ฆญํ„ฐ์˜ ์ขŒํ‘œ ์ถœ์ฒ˜:ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋ฌธ์ œ์„ค๋ช… ๋จธ์“ฑ์ด๋Š” RPG๊ฒŒ์ž„์„ ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒŒ์ž„์—๋Š” up, down, left, right ๋ฐฉํ–ฅํ‚ค๊ฐ€ ์žˆ์œผ๋ฉฐ ๊ฐ ํ‚ค๋ฅผ ๋ˆ„๋ฅด๋ฉด ์œ„, ์•„๋ž˜, ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํ•œ ์นธ์”ฉ ์ด๋™ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด [0,0]์—์„œ up์„ ๋ˆ„๋ฅธ๋‹ค๋ฉด ์บ๋ฆญํ„ฐ์˜ ์ขŒํ‘œ๋Š” [0, 1], down์„ ๋ˆ„๋ฅธ๋‹ค๋ฉด [0, -1], left๋ฅผ ๋ˆ„๋ฅธ๋‹ค๋ฉด [-1, 0], right๋ฅผ ๋ˆ„๋ฅธ๋‹ค๋ฉด [1, 0]์ž…๋‹ˆ๋‹ค. ๋จธ์“ฑ์ด๊ฐ€ ์ž…๋ ฅํ•œ ๋ฐฉํ–ฅํ‚ค์˜ ๋ฐฐ์—ด keyinput์™€ ๋งต์˜ ํฌ๊ธฐ board์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์บ๋ฆญํ„ฐ๋Š” ํ•ญ์ƒ [0,0]์—์„œ ์‹œ์ž‘ํ•  ๋•Œ ํ‚ค ์ž…๋ ฅ์ด ๋ชจ๋‘ ๋๋‚œ ๋’ค์— ์บ๋ฆญํ„ฐ์˜ ์ขŒํ‘œ [x, y]๋ฅผ returnํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”. [0, 0]์€ board์˜ ์ • ์ค‘์•™์— ์œ„์น˜ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด board์˜ ๊ฐ€๋กœ ํฌ๊ธฐ๊ฐ€ 9๋ผ๋ฉด ์บ๋ฆญํ„ฐ๋Š” ์™ผ์ชฝ์œผ๋กœ ์ตœ๋Œ€ [-4, 0]๊นŒ์ง€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ตœ๋Œ€ [4, 0]๊นŒ์ง€ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด ๋ฌธ์ œ๋Š” ์ฃผ์–ด์ง„ ์ด๋™ํ•˜๋Š” ์ขŒํ‘œ๋ฅผ ๊ทธ๋Œ€๋กœ ๋งคํ•‘ ๊ฐ์ฒด๋กœ ์„ค์ •ํ•ด ๋‘๊ณ , ์‹œ์ž‘์ขŒํ‘œ๋“ค์„ ์ˆœํšŒํ•˜๋ฉด์„œ board์˜ ๊ฒฝ๊ณ„๋ฅผ ํŒ๋‹จํ•˜์—ฌ ๊ฒฝ๊ณ„ ๋‚ด์— ์žˆ๋‹ค๋ฉด ํ˜„์žฌ ์ขŒํ‘œ์™€ ์ˆœํšŒํ•˜๋Š” ์‹œ์ž‘ ์ขŒํ‘œ๋ฅผ ๋”ํ•ด์ค€๋‹ค.

function solution(keyinput, board) { const controlMapper = { left: [-1, 0], right: [1, 0], up: [0, 1], down: [0, -1], } let cur = [0, 0] //์‹œ์ž‘ ์ขŒํ‘œ for (const key of keyinput) { const [a, b] = controlMapper[key] const [curA, curB] = cur const w = Math.floor(board[0] / 2) //๊ฐ€๋กœ ์ขŒํ‘œ const h = Math.floor(board[1] / 2) //์„ธ๋กœ ์ขŒํ‘œ // ์ฃผ์–ด์ง„ board ์˜ ๊ฒฝ๊ณ„๋ฅผ ๋ฒ—์–ด๋‚˜๋ฉด ์ž…๋ ฅ ๋ฌด์‹œ if (-w > curA + a || w < curA + a || curB + b > h || curB + b < -h) continue cur = [a + curA, b + curB] } return cur }

Hi, I'm Hyunsu ๐Ÿ‘‹

Profile Image

์•ˆ๋…•ํ•˜์„ธ์š”. ํ”„๋ก ํŠธ์—”๋“œ ๊ฐœ๋ฐœ์ž ์ฃผํ˜„์ˆ˜์ž…๋‹ˆ๋‹ค.

๊ฐœ๋ฐœ์„ ํ†ตํ•ด ์‚ฌ์šฉ์ž๋“ค์—๊ฒŒ ํ’๋ถ€ํ•˜๊ณ  ๊ฐ€์น˜ ์žˆ๋Š” ๊ฒฝํ—˜์„ ์ œ๊ณตํ•˜๋Š” ์ผ์— ๋ฟŒ๋“ฏํ•จ์„ ๋Š๋‚๋‹ˆ๋‹ค.

์˜ต์‹œ๋””์–ธ(Obsidian)์—์„œ ํ˜„์žฌ ๋ธ”๋กœ๊ทธ๋กœ ํ•˜๋‚˜์”ฉ ๊ธ€์„ ์˜ฎ๊ธฐ๋Š” ๊ณผ์ •์— ์žˆ์–ด์š”. โ˜•๏ธ ๐Ÿ‘ฉโ€๐Ÿ’ป โ›ท

Github on ViewReach Me Out