๐ก๋ฌธ์ ๋ถ์ ์์ฝ
๋ฌธ์ ์ค๋ช
- ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ์ฌ๋ฌ ๊ฐ์ ๊ดํธ ๋ฌธ์์ด์ด ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด(Valid Parenthesis String, VPS)์ธ์ง ํ์ธํ๋ ๋ฌธ์
- ๊ดํธ ๋ฌธ์์ด์ด ์ฌ๋ฐ๋ฅธ ๊ฒฝ์ฐ "YES"๋ฅผ ์ถ๋ ฅํ๊ณ , ๊ทธ๋ ์ง ์์ผ๋ฉด "NO"๋ฅผ ์ถ๋ ฅํด์ผ ํ๋ค.
์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด(VPS)
- ๊ดํธ ๋ฌธ์์ด์์ ๊ฐ ์ฌ๋ ๊ดํธ
(
๋ ๋ฐ๋์ ๋ซ๋ ๊ดํธ )
์ ์ง์ด ๋ง์์ผ ํ๋ค.
- ๊ดํธ์ ์์๋ ์ค์ํ๋ค.
์ฌ๋ ๊ดํธ๊ฐ ๋จผ์ ๋์ค๊ณ ๊ทธ์ ๋์ํ๋ ๋ซ๋ ๊ดํธ๊ฐ ๋์์ผ ํ๋ค.
()()
๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด์ด๋ค.
(())
๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด์ด๋ค.
)(
๋ ์ฌ๋ฐ๋ฅด์ง ์์ ๋ฌธ์์ด์ด๋ค. ์ฌ๋ ๊ดํธ๊ฐ ๋์ค๊ธฐ ์ ์ ๋ซ๋ ๊ดํธ๊ฐ ๋์๊ธฐ ๋๋ฌธ์ด๋ค.
(()
๋ ์ฌ๋ฐ๋ฅด์ง ์๋ค. ๋ซ๋ ๊ดํธ๊ฐ ๋ถ์กฑํ๋ค.
๐ก์๊ณ ๋ฆฌ์ฆ ์ค๊ณ
- ๊ฐ ๊ดํธ ๋ฌธ์์ด์ ์์ฐจ์ ์ผ๋ก ํ์ธ
- ์ฌ๋ ๊ดํธ
(
๊ฐ ๋์ค๋ฉด ์นด์ดํธ๋ฅผ ์ฆ๊ฐ์ํค๊ณ , ๋ซ๋ ๊ดํธ )
๊ฐ ๋์ค๋ฉด ์นด์ดํธ๋ฅผ ๊ฐ์์ํจ๋ค.
- ์ค๊ฐ์ ์นด์ดํธ๊ฐ ์์๊ฐ ๋๋ ๊ฒฝ์ฐ
: ์ด๋ ๋ซ๋ ๊ดํธ๊ฐ ์ฌ๋ ๊ดํธ๋ณด๋ค ๋จผ์ ๋์จ๋ค๋ ์๋ฏธ๋ก, ์ด๋๋ ์ฆ์ "NO"๋ก ํ๋จํ ์ ์๋ค.
- ๋ง์ง๋ง์ ์นด์ดํธ๊ฐ 0์ธ์ง ํ์ธ
: ๋ชจ๋ ๊ดํธ๋ฅผ ํ์ธํ ํ์ ์นด์ดํธ๊ฐ 0์ด๋ฉด ์ฌ๋ ๊ดํธ์ ๋ซ๋ ๊ดํธ์ ์๊ฐ ์ ํํ ๋ง๋ ๊ฒ์ด๋ฏ๋ก "YES"์ด๋ค. ๊ทธ๋ ์ง ์์ผ๋ฉด "NO"๋ก ํ๋จํ๋ค.
- ๊ณผ์
- ๊ฐ ๊ดํธ ๋ฌธ์์ด์ ์ํํ๋ฉฐ ์ฌ๋ ๊ดํธ์ ๋ซ๋ ๊ดํธ์ ์๋ฅผ ์ธ๊ณ , ๋ถ๊ท ํ์ด ๋ฐ์ํ๊ฑฐ๋ ๊ดํธ์ ์์๊ฐ ์๋ชป๋๋ฉด ๋ฐ๋ก "NO"๋ฅผ ๋ฐํํ๋ค.
- ๊ดํธ ๋ฌธ์์ด์ด ๋๊น์ง ๊ท ํ์ ๋ง์ถ๋ฉด "YES"๋ฅผ ๋ฐํํ๋ค.
๋จ๊ณ
- ์
๋ ฅ ์ฒ๋ฆฌ: ์ฌ๋ฌ ์ค์ ๊ฑธ์ณ ๊ดํธ ๋ฌธ์์ด์ด ์ฃผ์ด์ง๋ฏ๋ก ์ด๋ฅผ ๋ฐฐ์ด ํํ๋ก ๋ฐ์ ์ฒ๋ฆฌํ๋ค.
- ์นด์ดํธ ๋ณ์ ์ฌ์ฉ: ์ฌ๋ ๊ดํธ๋ ์นด์ดํธ๋ฅผ 1 ์ฆ๊ฐ, ๋ซ๋ ๊ดํธ๋ 1 ๊ฐ์์ํค๋ ๋ฐฉ์์ผ๋ก ๊ท ํ์ ํ์ธํ๋ค.
- ์์ ๋ถ๊ท ํ ํ์ธ: ๋ง์ฝ ์ค๊ฐ์ ์นด์ดํธ๊ฐ ์์๊ฐ ๋๋ฉด ์ฆ์ "NO"๋ฅผ ์ถ๋ ฅํ๊ณ ๋ค์ ๋ฌธ์์ด๋ก ๋์ด๊ฐ๋ค.
- ์ต์ข
๊ฒฐ๊ณผ ํ์ธ: ๋ฌธ์์ด์ ๋ชจ๋ ํ์ธํ ํ ์นด์ดํธ๊ฐ 0์ด๋ฉด "YES", ๊ทธ๋ ์ง ์์ผ๋ฉด "NO"๋ฅผ ์ถ๋ ฅํ๋ค.