avatar
Published on

Codility - Stone Wall

Author
  • avatar
    Name
    yceffort

StoneWall

๋ฌธ์ œ

๋Œ์€ N๋ฏธํ„ฐ ๊ธธ์ด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์œผ๋ฉฐ, ๋‘๊ป˜๋Š” ๋ชจ๋‘ ์ผ์ •ํ•˜๋‹ค. ๋ฐฐ์–ผ์— ๋Œ ๋†’์ด๊ฐ€ ์ฃผ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ์•„๋ž˜์™€ ๊ฐ™์ด ํ•ด์„ํ•  ์ˆ˜ ์žˆ๋‹ค.

  • H[i]: ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ฒฝ์˜ ๋†’์ด
  • H[0]: ๋ฒฝ ์™ผ์ชฝ ๋์˜ ๋†’์ด
  • H[N-1]: ๋ฒฝ ๋งˆ์ง€๋ง‰ ๋์˜ ๋†’์ด
H[0] = 8    H[1] = 8    H[2] = 5
H[3] = 7    H[4] = 9    H[5] = 8
H[6] = 7    H[7] = 4    H[8] = 8

๋Š” 7์„ ๋ฆฌํ„ดํ•ด์•ผ ํ•˜๋Š”๋ฐ, ๊ทธ ์ด์œ ๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

https://codility-frontend-prod.s3.amazonaws.com/media/task_static/stone_wall/static/images/auto/4f1cef49cc46d451e88109d449ab7975.png

ํ’€์ด

function solution(H) {
  const stack = []
  let count = 0

  for (let i = 0; i < H.length; i++) {
    // ๋ฒ ์ด์Šค๊ฐ€ ๋Œ์„ ์ฐพ๋Š”๋‹ค.
    // ๋ฒ ์ด์Šค๊ฐ€ ๋  ๋Œ์€ ๋ฌด์กฐ๊ฑด ํ•˜๋‚˜ ์žˆ์–ด์•ผ ํ•˜๊ณ 
    // ํ˜„์žฌ ์Œ“์œผ๋ ค๋Š” ๋Œ ์œ„์น˜๋ณด๋‹ค ๋‚ฎ์•„์•ผ ํ•œ๋‹ค.
    while (stack.length > 0 && stack[stack.length - 1] > H[i]) {
      stack.pop()
    }

    // ๋Œ ๋ช…๋‹จ์ด ๋น„์–ด์žˆ๊ฑฐ๋‚˜, ์ƒˆ๋กœ ์Œ“์•„์•ผ ํ•  ๋Œ์ด ์Šคํƒ์˜ ๋งˆ์ง€๋ง‰ ๋Œ ๋ณด๋‹ค ๋†’๋‹ค๋ฉด ์ƒˆ๋กœ ์Œ“๋Š”๋‹ค.
    if (stack.length === 0 || stack[stack.length - 1] < H[i]) {
      // ์ƒˆ๋กœ ์Œ“๊ณ  ์ง€๊ธˆ ๋†’์ด๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค.
      stack.push(H[i])
      count += 1
    }
  }

  return count
}

https://app.codility.com/demo/results/trainingTEZQDK-37Z/