- Published on
Codility - Stone Wall
- Author
- 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์ ๋ฆฌํดํด์ผ ํ๋๋ฐ, ๊ทธ ์ด์ ๋ ์๋์ ๊ฐ๋ค.
ํ์ด
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
}