#1439

처음에 문제를 봤을 때 이렇게 풀어야겠다! 라는 생각이 바로 들지는 않았다. 조금 생각하는 시간이 필요했고 바로 생각해냈다. 서지원! 서지원! 서지원!

문자열을 어떻게 어떤 순서로 바꿔주던지 결론은 항상 전부 0이거나 전부 1이다.

answer0 = 0
# 다 0인 경우
answer1 = 0
# 다 1인 경우
beforeWord0 = "0"
beforeWord1 = "1"

for i in range(len(S)):
    if S[i] != "0":
        if beforeWord0 == "0":
            beforeWord0 = "1"
            answer0 += 1
    else:
        beforeWord0 = "0"

for i in range(len(S)):
    if S[i] != "1":
        if beforeWord1 == "1":
            beforeWord1 = "0"
            answer1 += 1
    else:
        beforeWord1 = "1"

if answer0 < answer1:
    print(answer0)
else:
    print(answer1)

시간 복잡도는 O(2N)이다. 상수를 제거하고 생각할 수 있으므로 O(N)이라고 할 수 있다. 문제 분류가 그리디 알고리즘이라고 나오는데 이게 왜 그리디 알고리즘인지 잘 이해가 되지 않는다. 종종 오셔서 댓글 달아주고 가시는 고수분들 계시는데 ㅎㅎ 댓글로 설명해주시면 너무 감사합니다 🤓

맞췄습니다!!! 를 띄우고 나서 구글링을 했다. 얼마나 더 좋은 풀이가 있을까?

---

출처 - < ju_h2.log - 백준 1439. 뒤집기 풀이 >

s = input()
change = []
for i in range(1, len(s)):
    if s[i-1] != s[i]:
        change.append(i)
isOdd = False
if len(change)%2 == 1: 
    isOdd = True
    
result = len(change)//2
if isOdd:
    result += 1
print(result)

풀이를 보자마자 든 생각은

1. 이렇게 풀 수도 있구나...
2. 진짜 진지하게 다른 사람 풀이를 안보고 이걸 생각해낼 수 있다고?

이렇게 기록도 해놨으니 이런 문제 풀이도 있다는걸 이해하고 받아 들이고 다음에 유사한 문제가 나오면 써먹어야겠다.

내가 푼 방식과 런타임 시간은 정확히 똑같이 나온다.