๋ฌธ์ ์ค๋ช
์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๋, ์ํ๋ฒณ ์๋ฌธ์๋ก ์ด๋ฃจ์ด์ง ๋ฌธ์์ด์ ๊ฐ์ง๊ณ ์์ํฉ๋๋ค. ๋จผ์ ๋ฌธ์์ด์์ ๊ฐ์ ์ํ๋ฒณ์ด 2๊ฐ ๋ถ์ด ์๋ ์ง์ ์ฐพ์ต๋๋ค. ๊ทธ๋ค์, ๊ทธ ๋์ ์ ๊ฑฐํ ๋ค, ์๋ค๋ก ๋ฌธ์์ด์ ์ด์ด ๋ถ์ ๋๋ค. ์ด ๊ณผ์ ์ ๋ฐ๋ณตํด์ ๋ฌธ์์ด์ ๋ชจ๋ ์ ๊ฑฐํ๋ค๋ฉด ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๊ฐ ์ข ๋ฃ๋ฉ๋๋ค. ๋ฌธ์์ด S๊ฐ ์ฃผ์ด์ก์ ๋, ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ๋ฅผ ์ฑ๊ณต์ ์ผ๋ก ์ํํ ์ ์๋์ง ๋ฐํํ๋ ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์. ์ฑ๊ณต์ ์ผ๋ก ์ํํ ์ ์์ผ๋ฉด 1์, ์๋ ๊ฒฝ์ฐ 0์ ๋ฆฌํดํด์ฃผ๋ฉด ๋ฉ๋๋ค.
์๋ฅผ ๋ค์ด, ๋ฌธ์์ด S = baabaa ๋ผ๋ฉด
b aa baa → bb aa → aa →
์ ์์๋ก ๋ฌธ์์ด์ ๋ชจ๋ ์ ๊ฑฐํ ์ ์์ผ๋ฏ๋ก 1์ ๋ฐํํฉ๋๋ค.
์ ํ ์ฌํญ
- ๋ฌธ์์ด์ ๊ธธ์ด : 1,000,000์ดํ์ ์์ฐ์
- ๋ฌธ์์ด์ ๋ชจ๋ ์๋ฌธ์๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
์
์ถ๋ ฅ ์
s | result |
baabaa | 1 |
cdcd | 0 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์ ์ถ๋ ฅ ์ #2 : ๋ฌธ์์ด์ด ๋จ์์์ง๋ง ์ง์ง์ด ์ ๊ฑฐํ ์ ์๋ ๋ฌธ์์ด์ด ๋ ์ด์ ์กด์ฌํ์ง ์๊ธฐ ๋๋ฌธ์ 0์ ๋ฐํํฉ๋๋ค.
๋์ ์๋ฃจ์ (์ ๊ทผ ๋ฐฉ๋ฒ)
์ฒซ ๊ธ์๋ถํฐ ์์ฐจ์ ์ผ๋ก ๋น๊ตํด์ ์ผ์นํ ๊ฒฝ์ฐ index ์ ์ ๊ทผํด ๊ธ์๋ฅผ ์ ๊ฑฐํ๋ ค ํ๋๋ ์๊ฐ ๋ณต์ก๋๊ฐ ํ์ ์ด์์ผ๋ก ์ปค์ง ๊ฒ ๊ฐ์๋ค. ๊ทธ๋์ ํ์ฉํ ์ ์๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์๊ฐํด๋ณด๋ค๊ฐ ๋ฌธ๋ ์ ๊ธ์ ๋๋ ๋ง์ง๋ง ๊ธ์๋ถํฐ stack ์ ๋ด์๋๊ณ ์๋ก ๊บผ๋ด๋ ๊ธ์์ ๋น๊ตํ๋ ํํ๋ก ํ์ฉํ ์ ์์ ๊ฒ์ด๋ผ ์๊ฐํ๋ค.
๊ทธ ๊ฒฐ๊ณผ ๋ค์๊ณผ ๊ฐ์ ์ฝ๋๋ฅผ ์งค ์ ์์๋ค.
def solution(s):
# ๋ง์ง๋ง ๊ธ์๋ฅผ ๋นผ์ ๋ด์์ค stack
stack = []
case = list(s)
while len(case) > 0:
cur = case.pop()
# ๋ฌธ์์ด์ ๋ง์ง๋ง ๊ธ์์ stack ์ top ์ด ๋ค๋ฅผ ๊ฒฝ์ฐ, stack ์ ๋ด์์ค๋ค
if len(stack) == 0 or stack[-1] != cur:
stack.append(cur)
# ์ผ์นํ ๊ฒฝ์ฐ, ๋ ๋ค pop() ์ผ๋ก ๋นผ ์ค๋ค
elif stack[-1] == cur:
stack.pop()
return int(bool(len(stack)==0))
๋๊ธ