๐ ์์์ ๊ดํธ ์
๐ซ ์ ์
32 - {6 - (2 + 4) * 7}
-> {()}
O
5 + {6 - (12 + 4} * 7)
-> {(})
X
์ฃผ์ด์ง ๊ดํธ ๋ฌธ์์ด์ด ์ฌ๋ฐ๋ฅธ์ง/๊ท ํ์กํ๋์ง ํ๋จํ๋ ๋ฌธ์ .
๐ซง ๊ดํธ๊ฐ ํ ์ข ๋ฅ์ผ ๋
- ์์ชฝ๋ถํฐ ์ง์ ๋ง์ถฐ ์ง์๋๊ฐ๋ค, ๋ชจ๋ ์ง์์ง๋ค๋ฉด ์ฌ๋ฐ๋ฅธ ๋ฌธ์์ด
- ์ฌ๋ ๊ดํธ์ ๋ซ๋ ๊ดํธ ์๋ฅผ ๋น๊ตํ๋ค, ์๊ฐ ๋ค๋ฅด๋ฉด ์ฌ๋ฐ๋ฅด์ง ์์ ๋ฌธ์์ด
- ์๊ฐ ๊ฐ๋ค๊ณ ์ฌ๋ฐ๋ฅธ ๋ฌธ์์ด์ธ ๊ฒ์ ์๋ (i.e.
))((
)
- ์๊ฐ ๊ฐ๋ค๊ณ ์ฌ๋ฐ๋ฅธ ๋ฌธ์์ด์ธ ๊ฒ์ ์๋ (i.e.
๐ซง ๊ดํธ๊ฐ ์ฌ๋ฌ ์ข ๋ฅ์ผ ๋
- ์์ชฝ๋ถํฐ ์ง์ ๋ง์ถฐ ์ง์๋๊ฐ๋ค, ๋ชจ๋ ์ง์์ง๋ค๋ฉด ์ฌ๋ฐ๋ฅธ ๋ฌธ์์ด
๐ซง ๊ด์ฐฐ
๋ฌธ์์ด์ ์์์๋ถํฐ ์ฝ์ด๋๊ฐ ๋,
๋ซ๋ ๊ดํธ๋ ๋จ์์๋ ๊ดํธ ์ค์์ ๊ฐ์ฅ ์ต๊ทผ์ ๋ค์ด์จ ์ฌ๋ ๊ดํธ์ ์ง์ ์ง์ด ์์ ๋ฒ๋ฆฌ๋ ๋ช
๋ น์ด๋ผ๊ณ ์๊ฐํด๋ ๋๋ค.
๐ซ Solve By Stack
๐ซง ์ Why
๋ฐฐ์ด์ ์ด์ฉํ ๊ตฌํ
์ต๋ N๋ฒ ์ค๊ฐ ์์์ ์ญ์ ๊ฐ ๋ฐ์ O(N2)
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ด์ฉํ ๊ตฌํ
O(N)
๐ซง ๊ตฌํ
์ฌ๋ ๊ดํธ๋ฅผ ์ฝ์ ๋ ๋ง๋ค ์ ์ฅํ๋ค๊ฐ ๋ซ๋ ๊ดํธ๋ฅผ ์ฝ์ ๋ ๊ฐ์ฅ ์ต๊ทผ์ ๋ค์ด์จ, ์ฆ ๊ฐ์ฅ ๋์ ์๋ ์ฌ๋ ๊ดํธ์ ์ง์ ์ด๋ฃจ๊ฒ ํด์ฃผ๊ณ pop๋ฅผ ํ๋ฉด ์ฌ๋ฐ๋ฅธ ๊ดํธ ์์ธ์ง ํ์ธํ ์ ์๋ค.
- ์ฌ๋ ๊ดํธ๊ฐ ๋์ค๋ฉด ์คํ์ ์ถ๊ฐ
- ๋ซ๋ ๊ดํธ๊ฐ ๋์์ ๊ฒฝ์ฐ,
- ์คํ์ด ๋น์ด์์ผ๋ฉด ์ฌ๋ฐ๋ฅด์ง ์์ ๊ดํธ ์
- ์คํ์ top์ด ์ง์ด ๋ง์ง ์๋ ๊ดํธ์ผ ๊ฒฝ์ฐ ์ฌ๋ฐ๋ฅด์ง ์์ ๊ดํธ ์
- ์คํ์ top์ด ์ง์ด ๋ง๋ ๊ดํธ์ผ ๊ฒฝ์ฐ pop
- ๋ชจ๋ ๊ณผ์ ์ ๋๋ธ ํ ์คํ์ ๊ดํธ๊ฐ ๋จ์์์ผ๋ฉด ์ฌ๋ฐ๋ฅด์ง ์์ ๊ดํธ ์, ๋จ์์์ง ์์ผ๋ฉด ์ฌ๋ฐ๋ฅธ ๊ดํธ ์
๐ซง ๋ฐฑ์ค
์ด ๊ธฐ์ฌ๋ ์ ์๊ถ์์ CC BY 4.0 ๋ผ์ด์ผ์ค๋ฅผ ๋ฐ๋ฆ
๋๋ค.