๐Ÿฑโ€๐Ÿ‘ค[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๊ธธ ์ฐพ๊ธฐ ๊ฒŒ์ž„

Chobbyยท2022๋…„ 4์›” 28์ผ
0

Programmers

๋ชฉ๋ก ๋ณด๊ธฐ
31/344
post-thumbnail

๋ฌธ์ œ ์„ค๋ช…

๊ธธ ์ฐพ๊ธฐ ๊ฒŒ์ž„

์ „๋ฌด๋กœ ์Šน์ง„ํ•œ ๋ผ์ด์–ธ์€ ๊ธฐ๋ถ„์ด ๋„ˆ๋ฌด ์ข‹์•„ ํ”„๋ Œ์ฆˆ๋ฅผ ์ด๋Œ๊ณ  ํŠน๋ณ„ ํœด๊ฐ€๋ฅผ ๊ฐ€๊ธฐ๋กœ ํ–ˆ๋‹ค.
๋‚ด์นœ๊น€์— ์—ฌํ–‰ ๊ณ„ํš๊นŒ์ง€ ๊ตฌ์ƒํ•˜๋˜ ๋ผ์ด์–ธ์€ ์žฌ๋ฏธ์žˆ๋Š” ๊ฒŒ์ž„์„ ์ƒ๊ฐํ•ด๋ƒˆ๊ณ  ์—ญ์‹œ ์ „๋ฌด๋กœ ์Šน์ง„ํ• ๋งŒํ•œ ์ธ์žฌ๋ผ๊ณ  ์Šค์Šค๋กœ์—๊ฒŒ ๊ฐํƒ„ํ–ˆ๋‹ค.

๋ผ์ด์–ธ์ด ๊ตฌ์ƒํ•œ(๊ทธ๋ฆฌ๊ณ  ์•„๋งˆ๋„ ๋ผ์ด์–ธ๋งŒ ์ฆ๊ฑฐ์šธ๋งŒํ•œ) ๊ฒŒ์ž„์€, ์นด์นด์˜ค ํ”„๋ Œ์ฆˆ๋ฅผ ๋‘ ํŒ€์œผ๋กœ ๋‚˜๋ˆ„๊ณ , ๊ฐ ํŒ€์ด ๊ฐ™์€ ๊ณณ์„ ๋‹ค๋ฅธ ์ˆœ์„œ๋กœ ๋ฐฉ๋ฌธํ•˜๋„๋ก ํ•ด์„œ ๋จผ์ € ์ˆœํšŒ๋ฅผ ๋งˆ์นœ ํŒ€์ด ์Šน๋ฆฌํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

๊ทธ๋ƒฅ ์ง€๋„๋ฅผ ์ฃผ๊ณ  ๊ฒŒ์ž„์„ ์‹œ์ž‘ํ•˜๋ฉด ์žฌ๋ฏธ๊ฐ€ ๋œํ•ด์ง€๋ฏ€๋กœ, ๋ผ์ด์–ธ์€ ๋ฐฉ๋ฌธํ•  ๊ณณ์˜ 2์ฐจ์› ์ขŒํ‘œ ๊ฐ’์„ ๊ตฌํ•˜๊ณ  ๊ฐ ์žฅ์†Œ๋ฅผ ์ด์ง„ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ๊ฐ€ ๋˜๋„๋ก ๊ตฌ์„ฑํ•œ ํ›„, ์ˆœํšŒ ๋ฐฉ๋ฒ•์„ ํžŒํŠธ๋กœ ์ฃผ์–ด ๊ฐ ํŒ€์ด ์Šค์Šค๋กœ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๋„๋ก ํ•  ๊ณ„ํš์ด๋‹ค.

๋ผ์ด์–ธ์€ ์•„๋ž˜์™€ ๊ฐ™์€ ํŠน๋ณ„ํ•œ ๊ทœ์น™์œผ๋กœ ํŠธ๋ฆฌ ๋…ธ๋“œ๋“ค์„ ๊ตฌ์„ฑํ•œ๋‹ค.

  • ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๋ชจ๋“  ๋…ธ๋“œ์˜ x, y ์ขŒํ‘œ ๊ฐ’์€ ์ •์ˆ˜์ด๋‹ค.
  • ๋ชจ๋“  ๋…ธ๋“œ๋Š” ์„œ๋กœ ๋‹ค๋ฅธ x๊ฐ’์„ ๊ฐ€์ง„๋‹ค.
  • ๊ฐ™์€ ๋ ˆ๋ฒจ(level)์— ์žˆ๋Š” ๋…ธ๋“œ๋Š” ๊ฐ™์€ y ์ขŒํ‘œ๋ฅผ ๊ฐ€์ง„๋‹ค.
  • ์ž์‹ ๋…ธ๋“œ์˜ y ๊ฐ’์€ ํ•ญ์ƒ ๋ถ€๋ชจ ๋…ธ๋“œ๋ณด๋‹ค ์ž‘๋‹ค.
  • ์ž„์˜์˜ ๋…ธ๋“œ V์˜ ์™ผ์ชฝ ์„œ๋ธŒ ํŠธ๋ฆฌ(left subtree)์— ์žˆ๋Š” ๋ชจ๋“  ๋…ธ๋“œ์˜ x๊ฐ’์€ V์˜ x๊ฐ’๋ณด๋‹ค ์ž‘๋‹ค.
  • ์ž„์˜์˜ ๋…ธ๋“œ V์˜ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒ ํŠธ๋ฆฌ(right subtree)์— ์žˆ๋Š” ๋ชจ๋“  ๋…ธ๋“œ์˜ x๊ฐ’์€ V์˜ x๊ฐ’๋ณด๋‹ค ํฌ๋‹ค.

์•„๋ž˜ ์˜ˆ์‹œ๋ฅผ ํ™•์ธํ•ด๋ณด์ž.

๋ผ์ด์–ธ์˜ ๊ทœ์น™์— ๋งž๊ฒŒ ์ด์ง„ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ๋งŒ ์ขŒํ‘œ ํ‰๋ฉด์— ๊ทธ๋ฆฌ๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. (์ด์ง„ํŠธ๋ฆฌ์˜ ๊ฐ ๋…ธ๋“œ์—๋Š” 1๋ถ€ํ„ฐ N๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์–ด์žˆ๋‹ค.)

์ด์ œ, ๋…ธ๋“œ๋ฅผ ์ž‡๋Š” ๊ฐ„์„ (edge)์„ ๋ชจ๋‘ ๊ทธ๋ฆฌ๋ฉด ์•„๋ž˜์™€ ๊ฐ™์€ ๋ชจ์–‘์ด ๋œ๋‹ค.

์œ„ ์ด์ง„ํŠธ๋ฆฌ์—์„œ ์ „์œ„ ์ˆœํšŒ(preorder), ํ›„์œ„ ์ˆœํšŒ(postorder)๋ฅผ ํ•œ ๊ฒฐ๊ณผ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๊ณ , ์ด๊ฒƒ์€ ๊ฐ ํŒ€์ด ๋ฐฉ๋ฌธํ•ด์•ผ ํ•  ์ˆœ์„œ๋ฅผ ์˜๋ฏธํ•œ๋‹ค.

  • ์ „์œ„ ์ˆœํšŒ : 7, 4, 6, 9, 1, 8, 5, 2, 3
  • ํ›„์œ„ ์ˆœํšŒ : 9, 6, 5, 8, 1, 4, 3, 2, 7

๋‹คํ–‰ํžˆ ๋‘ ํŒ€ ๋ชจ๋‘ ๋จธ๋ฆฌ๋ฅผ ๋ชจ์•„ ๋ถ„์„ํ•œ ๋์— ๋ผ์ด์–ธ์˜ ์˜๋„๋ฅผ ๊ฐ„์‹ ํžˆ ์•Œ์•„์ฐจ๋ ธ๋‹ค.

๊ทธ๋Ÿฌ๋‚˜ ์—ฌ์ „ํžˆ ๋ฌธ์ œ๋Š” ๋‚จ์•„์žˆ๋‹ค. ๋…ธ๋“œ์˜ ์ˆ˜๊ฐ€ ์˜ˆ์‹œ์ฒ˜๋Ÿผ ์ ๋‹ค๋ฉด ์‰ฝ๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ, ์˜ˆ์ƒ๋Œ€๋กœ ๋ผ์ด์–ธ์€ ๊ทธ๋ ‡๊ฒŒ ํ•  ์ƒ๊ฐ์ด ์ „ํ˜€ ์—†์—ˆ๋‹ค.

์ด์ œ ๋‹น์‹ ์ด ๋‚˜์„ค ๋•Œ๊ฐ€ ๋˜์—ˆ๋‹ค.

๊ณค๊ฒฝ์— ๋น ์ง„ ์นด์นด์˜ค ํ”„๋ Œ์ฆˆ๋ฅผ ์œ„ํ•ด ์ด์ง„ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๋…ธ๋“œ๋“ค์˜ ์ขŒํ‘œ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด nodeinfo๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ,
๋…ธ๋“œ๋“ค๋กœ ๊ตฌ์„ฑ๋œ ์ด์ง„ํŠธ๋ฆฌ๋ฅผ ์ „์œ„ ์ˆœํšŒ, ํ›„์œ„ ์ˆœํšŒํ•œ ๊ฒฐ๊ณผ๋ฅผ 2์ฐจ์› ๋ฐฐ์—ด์— ์ˆœ์„œ๋Œ€๋กœ ๋‹ด์•„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜์ž.

์ œํ•œ์‚ฌํ•ญ

  • nodeinfo๋Š” ์ด์ง„ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๊ฐ ๋…ธ๋“œ์˜ ์ขŒํ‘œ๊ฐ€ 1๋ฒˆ ๋…ธ๋“œ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ๋“ค์–ด์žˆ๋Š” 2์ฐจ์› ๋ฐฐ์—ด์ด๋‹ค.
    • nodeinfo์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 10,000 ์ดํ•˜์ด๋‹ค.
    • nodeinfo[i] ๋Š” i + 1๋ฒˆ ๋…ธ๋“œ์˜ ์ขŒํ‘œ์ด๋ฉฐ, [x์ถ• ์ขŒํ‘œ, y์ถ• ์ขŒํ‘œ] ์ˆœ์œผ๋กœ ๋“ค์–ด์žˆ๋‹ค.
    • ๋ชจ๋“  ๋…ธ๋“œ์˜ ์ขŒํ‘œ ๊ฐ’์€ 0 ์ด์ƒ 100,000 ์ดํ•˜์ธ ์ •์ˆ˜์ด๋‹ค.
    • ํŠธ๋ฆฌ์˜ ๊นŠ์ด๊ฐ€ 1,000 ์ดํ•˜์ธ ๊ฒฝ์šฐ๋งŒ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค.
    • ๋ชจ๋“  ๋…ธ๋“œ์˜ ์ขŒํ‘œ๋Š” ๋ฌธ์ œ์— ์ฃผ์–ด์ง„ ๊ทœ์น™์„ ๋”ฐ๋ฅด๋ฉฐ, ์ž˜๋ชป๋œ ๋…ธ๋“œ ์œ„์น˜๊ฐ€ ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ๋Š” ์—†๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

nodeinforesult
[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]][[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

๋ฌธ์ œ์— ์ฃผ์–ด์ง„ ์˜ˆ์‹œ์™€ ๊ฐ™๋‹ค.

๋‚˜์˜ ํ’€์ด

ํ•ด๋‹น ๋ฌธ์ œ์˜ ์ค‘์š” ํฌ์ธํŠธ๋Š” ์ „์œ„ ์ˆœํšŒ, ํ›„์œ„ ์ˆœํšŒ ๋ฐฉ๋ฒ•์ธ๋ฐ

// ์ „์œ„ ์ˆœํšŒ
function preOrder(val) {
  if(val !== null) {
    pre.push(val.idx)
    preOrder(val.left)
    preOrder(val.right)            
  }
}

// ํ›„์œ„ ์ˆœํšŒ
function postOrder(val) {
  if(val !== null) {
    postOrder(val.left)
    postOrder(val.right)      
    post.push(val.idx)
  }
}

์œ„ ์ฝ”๋“œ์—์„œ ์•Œ ์ˆ˜ ์žˆ๋“ฏ์ด ์–ด๋Š ํƒ€์ด๋ฐ์— ๋ฐฐ์—ด์— ๊ฐ’์„ ๋‹ด๋ƒ๋กœ ๊ตฌ๋ถ„ ํ•  ์ˆ˜ ์žˆ์Œ

๋”ฐ๋ผ์„œ ์ตœ์ข… ์ฝ”๋“œ๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

function solution(nodeinfo) {
    
    // ์ „์œ„ ๋ฐ ํ›„์œ„ ๋ฐฐ์—ด ์ƒ์„ฑ
    const pre = []
    const post = []
    
    // ๋…ธ๋“œ ํด๋ž˜์Šค๋ฅผ ์ƒ์„ฑํ•จ
    class Node {
        constructor(idx,x) {
            this.idx = idx
            this.x = x
            this.left = null
            this.right = null
        }
        
        _add(idx,x) {
            if(x <= this.x) {
                this._Left(idx,x)
            } else {
                this._Right(idx,x)
            }
        }
        _Left(idx,x) {
            if(this.left) {
                this.left._add(idx,x)
            } else {
                this.left = new Node(idx,x)
            }
        }
        _Right(idx,x) {
            if(this.right) {
                this.right._add(idx,x)
            } else {
                this.right = new Node(idx,x)
            }
        }
    }
    
    // y์ถ• ๊ธฐ์ค€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ๋…ธ๋“œ๋ฅผ ์ •๋ ฌ
    const infos = nodeinfo.map((node,idx) => [idx+1, node[0], node[1]]).sort((a,b) => b[2] - a[2])
    
    // y์ถ• ์ •๋ ฌ ๊ธฐ์ค€ ์ฒซ ๋ฒˆ์งธ ์š”์†Œ๊ฐ€ ์ตœ์ƒ๋‹จ ๋ถ€๋ชจ ๋…ธ๋“œ
    const startNode = new Node(infos[0][0],infos[0][1])
    
    // ๋…ธ๋“œ ์‚ฝ์ž…
    for(let i = 1; i < infos.length ; i ++) {
        startNode._add(infos[i][0],infos[i][1])
    }
    
    // ์ „์œ„ ์ˆœํšŒ
    function preOrder(val) {
        if(val !== null) {
            pre.push(val.idx)
            preOrder(val.left)
            preOrder(val.right)            
        }
    }
    
    // ํ›„์œ„ ์ˆœํšŒ
    function postOrder(val) {
        if(val !== null) {
            postOrder(val.left)
            postOrder(val.right)      
            post.push(val.idx)
        }
    }
    
    preOrder(startNode)
    postOrder(startNode)
    return [pre,post]
}
profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

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