๋ฐฑ์ค 1439 : ๋ค์ง๊ธฐ
ํ์ด
์นด์นด์ค ๊ณต์ฑ ๋ฌธ์ ์ค ํ๋์๋ ๋ฌธ์์ด ์์ถ์ ์ฌ์ด ๋ฒ์ ์ ๋๋ค.
๋ง์ฝ 00111000์ธ ๊ฒฝ์ฐ์ ๋ค์ง๊ธฐ ์๋, ์ด์ด์ ธ์๋ ๋์ผํ ์(00, 111, 000)์ ํ๋์ ์(0,1,0)๊ณผ ๊ฐ์ต๋๋ค. ๊ฐ๋ น 00111000์ ๋ค์ง๊ธฐ ์ํด์๋ ์ค๊ฐ์ ๊ฐ์ ์์ ์ด์ด์ง์ง ์์ 111์ ๋ค์ง์ผ๋ฉด ๋๋ฏ์ด, 010์์๋ ๋ง์ฐฌ๊ฐ์ง์ ๋๋ค.
์ด๋ฅผ ์ด์ฉํ์ฌ ์ฐ์ ์ด์ด์ง ์๋ฅผ ํ๋์ ์๋ก ์นํํ๋ ๋ฌธ์์ด ์์ถ์ ํด์ฃผ๊ณ , 0๊ณผ 1์ ๊ฐฏ์๋ฅผ ์ธ์ด ๋ ์ค ๋ ์์ ๊ฐ์ ์ถ๋ ฅํ๋ฉด ๋ฉ๋๋ค.
๋จ, ์ ์ํด์ผํ ์ ์ ์
๋ ฅ์ผ๋ก ๋ค์ด์ค๋ S๋ ์ต๋ 1,000,000์ ๊ฐ์ ์ง๋๋๋ค. ์ฆ 10^6์ผ๋ก, ํ ๋ฒ์ ์ํ(O(N))๋ก๋ง ์ฒ๋ฆฌํด์ผ ์๊ฐ์ด๊ณผ๋ฅผ ๋ฐ์ง ์์ ์ ์์ต๋๋ค. (10^8์ด ๋๋ต 1์ด ๊ฑธ๋ฆฝ๋๋ค.)
์ฝ๋
S = input()
ans = ""
N0 = 0
N1 = 0
for i in range(1, len(S)) :
if(S[i-1] != S[i]) :
ans += S[i-1]
if(S[i-1] == "0") : N0+=1
else : N1+=1
if(ans and (S[len(S)-1] != ans[len(ans)-1])) :
ans+=S[len(S)-1]
if(S[len(S)-1] == "0") : N0+=1
else : N1+=1
print(min(N0,N1))
ํด๋น ์ฝ๋์ ์๊ฐ ๋ณต์ก๋๋ ํ ๋ฒ ์ํํ๋ ๊ฒ์ผ๋ก ๋๋๋ฏ๋ก, O(N)์ ๋๋ค.