๋ฐฑ์ค 12782
๋ฌธ์ ๋งํฌ
๋์ด๋ : ์ค๋ฒ5
ํ์ด
ํด๋น ๋ฌธ์ ์์์ ์ฐ์ฐ์ ๋ ๊ฐ์ง์ ๋๋ค.
- 0์ 1๋ก, 1์ 0์ผ๋ก ๋ฐ๊พธ๊ฑฐ๋
- ๋ค๋ฅธ ์๋ฆฌ์ ์๋ผ๋ฆฌ ์์น๋ฅผ ๋ฐ๊พธ๋ ๊ฒ (0<->1 swap ์ฐ์ฐ)
๊ทธ๋ฌ๋ฏ๋ก ๋ง์ฝ ์ ๋ ฅ๋๋ ์ฒซ ๋ฒ์งธ ์ด์ง์๋ฅผ origin, ๋ ๋ฒ์งธ ์ด์ง์๋ฅผ dest๋ก origin์์ dest๋ก ๋ฐ๊พธ๋ ๊ฒ์ ๋ชฉ์ ์ผ๋ก ํ๊ณ , ์ต์ํ์ ์ฐ์ฐ์ผ๋ก ๋ฐ๊พผ๋ค๊ณ ๊ฐ์ ํ์์ ๋, origin๊ณผ dest๊ฐ ์ฐจ์ด๊ฐ ๋๋ ํํธ๋ ๋ ๊ฐ์ง ๊ฒฝ์ฐ์ ๋๋ค.
- origin bit๊ฐ 0์์ dest bit 1๋ก ๋ฐ๋
- origin bit๊ฐ 1์์ dest bit 0์ผ๋ก ๋ฐ๋
๋ ๊ฐ์ง ๊ฒฝ์ฐ๋ฐ์ ์์ผ๋ฏ๋ก, ๋ง์ฝ 0์์ 1๋ก ๋ฐ๋๋ ํ์๊ฐ N1, 1์์ 0์ผ๋ก ๋ฐ๋๋ ํ์๊ฐ N0์ด๋ผ ์๊ฐํด๋ณด๋ฉด, SWAP์ผ๋ก ํด๊ฒฐ ๊ฐ๋ฅํ ๋ถ๋ถ(abs(N1-N0)
)์ ํด๊ฒฐํ ํ, ๊ทธ๋๋ ๋ฐ๋์ง ์์๋ค๋ฉด ๋นํธ๋ฅผ ๋ฐ๊ฟ์ฃผ๋ฉด ๋๊ฒ ์ต๋๋ค. ์ด๋ ๋นํธ๋ฅผ ๋ฐ๊ฟ์ฃผ๋ ๊ฑด N0, N1 ์ค์ ์์ ์(min(N1,N0)
)์ ๋๋ค. ์๋ํ๋ฉด ๋ ํฐ ์์ ์์ ์์ ์ฐจ์ด ๋งํผ ์ด๋ฏธ SWAP์ผ๋ก ๋ฐ๊ฟจ๊ธฐ ๋๋ฌธ์ ๋๋ค.
์ฃผ์ํ ์ ์ ์๊ฐ ์ ํ์ 1์ด์ด๋ฉฐ, ์ต๋ 50๊ฐ์ ํ ์คํธ ์ผ์ด์ค, ์ต๋ 1,000,000(10^6)๋งํผ์ N์ด ์ ๋ ฅ๋ฉ๋๋ค. 10^8์ ์ฐ์ฐ๋์ด 1์ด ๊ฐ๋ ๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์, ๋จ ํ ๋ฒ๋ง์ ๋ฐ๋์ ๋น๊ต๋ฅผ ๋๋ด์ฃผ์ ์ผ ํฉ๋๋ค. ์๋์ ์ฝ๋๋ for loop 1ํ๋ง ์ฐฉ์คํ๊ฒ ์ํํ๋ O(N)์ผ๋ก ์๊ฐ ์ ํ ๋ด์ ๋ฐ๋์ ํต๊ณผํ๊ฒ ๋ฉ๋๋ค.
์ฝ๋
T = int(input())
for _ in range(T) :
a, b = input().split()
N0 = 0
N1 = 0
for i in range(len(a)) :
if(a[i] != b[i] and b[i] == '1') :
N1 += 1
elif (a[i] != b[i] and b[i] == '0') :
N0 += 1
print(min(N1,N0)+abs(N1-N0))