Logo
Hyunsu Blog
kakao-coding-test

๐Ÿ“†Published :Dec 8, 2023 โ€ข

๐Ÿ“†Updated :Dec 8, 2023 โ€ข

โ˜•๏ธ1min

2021 ์นด์นด์˜ค ์ฑ„ํƒ ์—ฐ๊ณ„ํ˜• ์ธํ„ด์‹ญ ํ‘œ ํŽธ์ง‘, ์Šคํƒ

๋“ค์–ด๊ฐ€๋ฉฐ

  • ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ๋ฌธ์ œ์˜ ์ •ํ™•๋„์™€ ํšจ์œจ์„ฑ์„ ๊ณ ๋ คํ•œ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ƒ๊ฐํ•ด ๋‚ด๋Š”๊ฒŒ ์‰ฝ์ง„ ์•Š๋‹ค.
  • ์ด๋ฒˆ ์Šคํ„ฐ๋””์—์„œ ์Šคํƒ,ํ๋ฅผ ์ง„ํ–‰ํ•˜๋ฉด์„œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ํ•ฉ๊ฒฉ์ž๋˜๊ธฐ์— ์ˆ˜๋ก ๋˜์–ด ์žˆ๋Š” ๋ฌธ์ œ์ธ 2021 ์นด์นด์˜ค ์ฑ„ํƒ ์—ฐ๊ณ„ํ˜• ์ธํ„ด์‰ฝ ๋ฌธ์ œ "ํ‘œ ํŽธ์ง‘"์—์„œ ๋ถ€๋ถ„์ ์œผ๋กœ ์Šคํƒ์„ ์ด์šฉํ•˜์˜€์ง€๋งŒ ๊ฒฐ๊ตญ์—” ํšจ์œจ์„ฑ ๋ถ€๋ถ„์—์„œ ์ž˜ ํ’€์–ด๋‚ด์ง€ ๋ชปํ–ˆ๋‹ค.
  • ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์„ ํƒํ•œ ์ด์œ ์™€ ํšจ์œจ์„ฑ์„ ๊ฐœ์„ ํ•˜๊ธฐ ์œ„ํ•ด ๋‹ค๋ฅธ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๊ณ ๋ คํ•  ์ˆ˜ ์žˆ๋Š” ์ด์œ ๋ฅผ ๋ณต๊ธฐํ•˜๋ฉฐ ๊ธ€์„ ์“ฐ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค
  • ๊ณจ๋“ ๋ž˜๋น— ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ํ•ฉ๊ฒฉ์ž ๋˜๊ธฐ ํŒŒ์ด์ฌ ํŽธ์˜ 6์žฅ ~ 7์žฅ ์จ๋จธ๋ฆฌ๊ฐ€ ํฌํ•จ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.

์Šคํƒ

๋จผ์ € ์Šคํƒ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด์ž.

  • ์Šคํƒ ๊ตฌ์กฐ๋ฅผ ์ดํ•ดํ•˜๋Š” ์˜ˆ๋กœ๋Š” ํ‹ฐ์Šˆ๋ฅผ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ํ‹ฐ์Šˆ๋ฅผ ์ฒ˜์Œ ๋งŒ๋“ค ๋• ๋จผ์ € ๋„ฃ์€ ํ‹ฐ์Šˆ๊ฐ€ ๊ฐ€์žฅ ์•„๋ž˜์— ์œ„์น˜ํ•œ๋‹ค.
  • ํ‹ฐ์Šˆ๋ฅผ ๋‹ค ๋งŒ๋“ค๊ณ  ๋‚˜์„œ ์‚ฌ์šฉํ•  ๋•Œ์—๋Š” ๋งจ ์œ„์— ์žˆ๋Š” ํ‹ฐ์Šˆ ๋ถ€ํ„ฐ ๋ฝ‘์œผ๋ฏ€๋กœ, ๊ฐ€์žฅ ๋‚˜์ค‘์— ๋„ฃ์€ ํ‹ฐ์Šˆ๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ๋จผ์ € ๋“ค์–ด๊ฐ„ ๊ฒƒ์ด ๋งˆ์ง€๋ง‰์— ๋‚˜์˜ค๋Š” ๊ทœ์น™์„ ๊ฐ–๊ณ  ์žˆ๋‹ค. (= ์„ ์ž…ํ›„์ถœ, First In Last Out, FIFO)

์Šคํƒ์˜ ADT

์ •์˜์„ค๋ช…๋ฆฌํ„ด ํƒ€์ž…
isFull()์Šคํƒ์— ๋“ค์–ด ์žˆ๋Š” ๋ฐ์ดํ„ฐ ๊ฐœ์ˆ˜๊ฐ€ maxsize๋ผ๋ฉด True, ์•„๋‹ˆ๋ฉด Falseboolean
isEmpty()์Šคํƒ์— ๋“ค์–ด ์žˆ๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ํ•˜๋‚˜๋ผ๋„ ์žˆ์œผ๋ฉด False, ์•„๋‹ˆ๋ฉด Trueboolean
push(ItemType item)์Šคํƒ์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๋Š”๋‹ค.void
pop()์Šคํƒ์—์„œ ๊ฐ€์žฅ ์ตœ๊ทผ์— ๋„ฃ์€ ๋ฐ์ดํ„ฐ๋ฅผ ๊บผ๋‚ด๊ณ , ๊ทธ ๋ฐ์ดํ„ฐ๋ฅผ ๋ฐ˜ํ™˜.Item Type
top์Šคํƒ์—์„œ ์ตœ๊ทผ ํ‘ธ์‹œํ•œ ๋ฐ์ดํ„ฐ์˜ ์œ„์น˜Int

2021 ์นด์นด์˜ค ์ฑ„ํƒ ์—ฐ๊ณ„ํ˜• ์ธํ„ด์‹ญ ํ‘œ ํŽธ์ง‘

๋‚˜์˜ ์ ‘๊ทผ๋ฒ•

๋‚ด๊ฐ€ ํ‘ผ ๋ฌธ์ œ์˜ ์ ‘๊ทผ ๋ฐฉ๋ฒ•์€, index๋ฅผ ์ด์šฉํ•˜์—ฌ up, down์‹œ ์ด๋™์„ ํ•˜๊ณ , ์‚ญ์ œ์˜ ๊ฒฝ์šฐ javascript์˜ delete ์—ฐ์‚ฐ์„ ์ด์šฉํ•˜์—ฌ ๋ฐฐ์—ด์˜ ๊ธธ์ด๋ฅผ ๋ณ€๊ฒฝํ•˜์ง€ ์•Š์€์ฑ„ undefined ๋กœ ๋ณ€๊ฒฝ ํ•œ ํ›„, index๋ฅผ ๋ฌธ์ œ ์กฐ๊ฑด์— ๋งž์ถ”์–ด ์œ„, ์•„๋ž˜๋กœ ๋ณ€๊ฒฝํ•˜์˜€๋‹ค. delete์‹œ ์ค‘์š”ํ•œ์ ์€ ๋ณต๊ตฌํ•  ๋•Œ ๊ฐ€์žฅ ์ตœ์‹ ์— ์ง€์šด ํ–‰์„ ๋‹ค์‹œ ๊ธฐ์–ตํ•ด์•ผ ํ•˜๋ฏ€๋กœ, delete ๋ฐ”๋กœ ์ „ stack์— ํ–‰์˜์ •๋ณด๋ฅผ ์ €์žฅํ•œ๋‹ค. ๋‚˜์˜ ๊ฒฝ์šฐ deletedStack = [[ํ–‰์˜ index, value]] ๋กœ ์ €์žฅํ–ˆ๋‹ค. ๊ทธ๋ž˜์„œ ๋ณต๊ตฌ์˜ ๊ฒฝ์šฐ deletedStack์„ pop ํ•˜์—ฌ ๊ธฐ์กด ๋ฐฐ์—ด์— undefined๋กœ ๋˜์–ด ์žˆ๋˜ ์š”์†Œ๋ฅผ row[index] = value ๋กœ ์žฌํ• ๋‹น ํ•ด์ฃผ์—ˆ๋‹ค.

ํ•˜์ง€๋งŒ ์ •ํ™•๋„ 29/30์— ํšจ์œจ์„ฑ 5/10 ์œผ๋กœ ์„ฑ๋Šฅ์„ ๋ฐ”๊พธ๋ ค ์ด๋ฆฌ์ €๋ฆฌ ์‹œ๋„ํ–ˆ์ง€๋งŒ, ๊ฒฐ๊ตญ ๋พฐ์กฑํ•œ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ฐพ์„ ์ˆ˜ ์—†์—ˆ๋‹ค. ์ฒ˜์Œ ์‹œ๋„ํ•œ ์ฝ”๋“œ๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

๋‚ด ์ฝ”๋“œ์˜ ๋ฌธ์ œ์ ์€

  1. ๋ฐฐ์—ด์—์„œ ์‚ญ์ œ ํ›„, up, down์„ ํ•  ๋•Œ ๋ชจ๋“  ์š”์†Œ๋“ค์„ ์ˆœํšŒํ•˜๋ฉด์„œ undefined ๊ฐ€ ์žˆ์œผ๋ฉด count์— ํฌํ•จํ•˜์ง€ ์•Š๋Š” ๋ฐฉ์‹์œผ๋กœ, ๋ชจ๋“  ์š”์†Œ๋ฅผ ์ˆœํšŒํ•œ๋‹ค๋Š” ์ ์ด๋‹ค.

  2. ์‚ญ์ œ ๋˜์—ˆ์„ ๋•Œ, ์‚ญ์ œ ๋œ ํ–‰์ด ๋ฐฐ์—ด์˜ ๋งˆ์ง€๋ง‰์ผ ๊ฒฝ์šฐ, ์„ ํƒ๋œ ํ–‰์„ ์‚ญ์ œ๋œ ํ–‰์˜ ๋ฐ”๋กœ ์œ„์˜ ์œ„์น˜์— ์žˆ๋Š” ํ–‰์œผ๋กœ ๋ณ€๊ฒฝ ํ•ด์•ผ ํ•˜๋Š”๋ฐ, ์ด ๊ณผ์ •์—์„œ ๋ฐฐ์—ด์˜ ๊ธธ์ด๋ฅผ ๋ณ€๊ฒฝํ•˜์ง€ ์•Š์•˜์œผ๋ฏ€๋กœ, ๋ฐฐ์—ด์˜ ๋งˆ์ง€๋ง‰ ํ–‰์ด undefined๊ฐ€ ์•„๋‹Œ ํ–‰์„ ๋˜ ์ฐพ๊ธฐ ์œ„ํ•ด ์ˆœํšŒ๋ฅผ ํ•ด์•ผ ํ•œ๋‹ค๋Š” ์ ์ด๋‹ค.

/** * ์ •ํ™•์„ฑ: 29/30, ํšจ์œจ์„ฑ 5/10 * @param {*} n * @param {*} k * @param {*} cmd * @returns */ function solution(n, k, cmd) { var answer = ""; let current = k; let row = Array.from({ length: n }, (v, i) => i); let deletedStack = []; for (const index in cmd) { const [direction, num = 0] = cmd[index].split(" "); if (direction === "D") { let temp = 0; let count = Number(num); while (count > 0 && current < row.length) { current = current += 1; if (row[current]) { count--; } } continue; } if (direction === "U") { let count = Number(num); while (count > 0 && current >= 0) { current = current - 1; if (row[current]) { count -= 1; } } continue; } if (direction === "C") { deletedStack.push([current, row[current]]); delete row[current]; //find next current let tempCurrent = current; let isFound = false; while (tempCurrent < row.length) { if (row[tempCurrent]) { isFound = true; break; } tempCurrent += 1; } if (isFound) { current = tempCurrent; } else { let temp = current; //๋ฐ˜๋Œ€๋กœ ์ž‘์•„์ ธ์•ผ ํ•จ. while (temp >= 0) { if (row[temp]) { current = temp; break; } temp--; } } continue; } if (direction === "Z") { //current๋Š” ๋ณ€๊ฒฝ x //restore const currentValue = row[current]; if (!deletedStack.length) continue; const [index, value] = deletedStack.pop(); row[index] = value; continue; } } // compare for (const num of row) { if (num === undefined) { answer += "X"; } else { answer += "O"; } } return answer; }

์ฑ…์„ ์ฐธ๊ณ ํ•œ ๋ฌธ์ œ ์ ‘๊ทผ๋ฒ•

  1. LinkedList ์ž๋ฃŒ๊ตฌ์กฐ์˜ ๊ฐœ๋…์„ ํ™œ์šฉํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์‚ญ์ œ ๋œ ํ–‰์ด ์žˆ๋‹ค๋ฉด, ์‚ญ์ œ๋œ ํ–‰์˜ ๊ธฐ์ค€์œผ๋กœ ์œ„, ์•„๋ž˜ ํ–‰ ์„ ๋ฐ”๋กœ ์—ฐ๊ฒฐ์‹œ์ผœ ์ค€๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ ๋‚ด ์ฝ”๋“œ์˜ ๋ฌธ์ œ์ ์ธ ๋ชจ๋“  ํ–‰์„ ์ˆœํšŒํ•  ํ•„์š”์—†์ด, ์‚ญ์ œ๋œ ํ–‰์„ ์ œ์™ธํ•˜๊ณ  ๊ทธ ๋‹ค์Œ ํ–‰์ด ์–ด๋””์ธ์ง€๋ฅผ O(1)์˜ ์ ‘๊ทผ์œผ๋กœ ํšจ์œจ์ ์ธ ์„ฑ๋Šฅ์„ ๋ณด์—ฌ์ค€๋‹ค.
stack // ์ •ํ™•๋„: 30, ํšจ์œจ์„ฑ: 70 function solution(n, k, cmd) { var answer = Array(n).fill("O"); let current = k+1; let deletedStack = []; let up = Array.from({ length: n+2 }, (v, i) => i-1); let down = Array.from({length: n+1},(v,i)=>i+1); for (const index in cmd){ const [direction, num = 0] = cmd[index].split(" "); if(direction === "C"){ deletedStack.push(current); up[down[current]] = up[current] down[up[current]] = down[current] current = n<down[current] ? up[current] : down[current]; continue; } if(direction === "Z"){ const deletedRow = deletedStack.pop(); down[up[deletedRow]] = deletedRow; up[down[deletedRow]] = deletedRow; continue } if(direction ==="U"){ for(let i =0; i<Number(num); i++){ current = up[current] } continue; } if(direction === "D"){ for(let i =0; i<Number(num); i++){ current = down[current] } continue; } } //์‚ญ์ œ๋œ ํ–‰์€ deletedStack์—์„œ ์ฐพ๋Š”๋‹ค. while(deletedStack.length){ const row = deletedStack.pop() answer[row-1] = "X" } return answer.join("") }

ํšŒ๊ณ 

  • ์‚ญ์ œ๋œ ํ–‰์ด ์žˆ์„ ๋•Œ ๋ถˆํ•„์š”ํ•œ ์—ฐ์‚ฐ์„ ์—†์• ๊ณ  ๋‹ค์Œ ํ–‰์ด ์–ด๋”˜์ง€๋ฅผ ์•Œ๋ฆฌ๋Š” LinkedList ๋ฅผ ์ƒ๊ฐ๋ชปํ•œ ๋ถ€๋ถ„์ด ์•„์‰ฌ์› ์ง€๋งŒ, ์ด๋ฒˆ ๊ธฐํšŒ์— ์ œ๋Œ€๋กœ ํ™œ์šฉํ•ด ๋ณผ ์ˆ˜ ์žˆ์—ˆ๋‹ค.

Hi, I'm Hyunsu ๐Ÿ‘‹

Profile Image

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

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

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

Github on ViewReach Me Out