Chapter4. ๋ฌธ์์ด
[๋ฌธ์ 9] ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ-Level2
์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๋ ์ํ๋ฒณ ์๋ฌธ์๋ก ์ด๋ฃจ์ด์ง ๋ฌธ์์ด์ ๊ฐ์ง๊ณ ์์ํฉ๋๋ค. ๋จผ์ ๋ฌธ์์ด์์ ๊ฐ์ ์ํ๋ฒณ์ด 2๊ฐ ๋ถ์ด์๋ ์ง์ ์ฐพ์ต๋๋ค. ๊ทธ๋ค์ ๋์ ์ ๊ฑฐํ ๋ค, ์๋ค๋ก ๋ฌธ์์ด์ ์ด์ด ๋ถ์
๋๋ค. ์ด ๊ณผ์ ์ ๋ฐ๋ณตํด์ ๋ฌธ์์ด์ ๋ชจ๋ ์ ๊ฑฐํ๋ค๋ฉด ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๊ฐ ์ข
๋ฃ๋ฉ๋๋ค. ๋ฌธ์์ด S๊ฐ ์ฃผ์ด์ก์ ๋, ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๋ฅผ ์ฑ๊ณต์ ์ผ๋ก ์ํํ ์ ์๋์ง ๋ฐํํ๋ ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ฑ๊ณต์ ์ผ๋ก ์ํํ ์ ์์ผ๋ฉด 1์, ์๋ ๊ฒฝ์ฐ 0์ ๋ฆฌํดํ๋ฉด ๋ฉ๋๋ค.
์๋ฅผ ๋ค์ด ๋ฌธ์์ด S = baabaa๋ผ๋ฉด b aa baa -> bb aa -> aa -> ์ ์์๋ก ๋ฌธ์์ด์ ๋ชจ๋ ์ ๊ฑฐํ ์ ์์ผ๋ฏ๋ก 1์ ๋ฐํํฉ๋๋ค.
- ๊ฐ์ ์ํ๋ฒณ 2๊ฐ ์ฐพ์์ ์ ๊ฑฐํ๊ธฐ
- ์ ๊ฑฐ๋ ๋ฌธ์์ด ํฉ์น๊ณ ์๋ ๋ฌธ์์ด์ ๋ฎ์ด์ฐ๊ธฐ
- ๋จ์ ๋ฌธ์์ด์ ๊ธธ์ด๊ฐ 1 ๋ฏธ๋ง์ด ๋ ๋๊น์ง 1~2๋ฒ ๋ฐ๋ณต
def solution(S):
while len(s) > 1:
s = list(S)
for i in range(len(s) - 1):
if s[i] == s[i+1]: s[i] = s[i+1] = ''
new_s = ''.join(s)
if len(s) == len(new_s) : break
s = new_s
return 1 if len(s) == 0 else 0
- ๋ฐ์ ๋ฌธ์์ด์ for๋ฌธ์ผ๋ก 1๊ธ์์ฉ ์ฝ๊ธฐ
- ๋ฐฐ์ด์ ์ํ๋ฒณ ํ๋์ฉ ๋ฃ๊ณ ๋ฐฐ์ด์ ๋ง์ง๋ง ์ํ๋ฒณ๊ณผ ํ์ฌ ์ํ ์ค์ธ ์ํ๋ฒณ์ด ๊ฐ๋ค๋ฉด ๋ฐฐ์ด์์ ํด๋น ์์ ์ ๊ฑฐํ๊ธฐ
- ๋ชจ๋ ๋ฌธ์์ด ๋์์ ๋ ๋ฑ
๋ ค์ ๊ฐ์ด ์๋ค๋ฉด ๋ชจ๋ ์ง์ง์ ๊ฒ, ๋จ์ ์๋ค๋ฉด ๋ชจ๋ ์ง์ง์ง ๋ชปํ ๊ฒ.
def solution(s):
stack = []
for case in s:
if stack and stack[-1] == case: stack.pop()
else: stack.append(case)
return 0 if stack else 1