백준 1439번: 뒤집기

본 문제는 백준에서 제공된 문제입니다.

1439번: 뒤집기

항상 문제를 풀기 전엔 이문제가 요구하는 게 무엇이고 이 문제를 어떤 방식으로 풀어야 할지 생각하고 코드를 짜기 시작해야 된다. 

이 문제가 요구하는 것은 결국 '주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.'이다.

결국 0과 1중 최적의 수가 뭘까 생각하다가 한값에 대해서만 결과를 내는 것이 아닌, 두 결과를 모두 구한 후에 두 개를 비교해서 반환하라는 것이다. (최적의 경우를 찾는 것이 아닌 두 가지의 모든 경우를 참고하는...)

즉, 0과 1로 경우를 나누어서 나온 횟수들에 대해서 최솟값을 반환하면 된다. → return min(all_zero, all_one)

그럼 이걸 어떤 방식으로 풀어야 될까? 일반 리스트? 스택? 큐? 연결리스트? ...

사실 이런 문제들은 어떤 풀어야 하는 정해진 유형이라기보다는, 직접 그 상황에서 떠올려야 하는 문제이다. 예를 들어, 그래프(map)-> BFS, DFS or DP 이런 식이 아닌, 그냥 일반 리스트를 다루는 문제이므로 그 상황에 맞는 풀이를 직접 짜내는 것이 핵심인 것 같다.

---

그럼 이제 이 문제가 원하는 풀이 방식을 알아보자.

먼저, 이 문자열의 처음 시작하는 문자가 0인지 1인지가 중요하다.

다시말해서 0→1,1→0 이든 바뀌고 나서의 문자가 무엇인지가 중요하다. (코드를 보면 이해가 가능하다)

문자가 0으로 시작한다 하면 내가 모든 문자를 0으로 만들고 싶을 때에는 당연히 바꿀 필요가 없어지는 것이고, 이 문자를 1로 바꾸고 싶다 하면 바꿀 필요가 있는 것이다. (1로 시작할 때도 마찬가지.)

그리고 이문제에서 핵심은 문자가 바뀌는 부분이다.(ex. 0→1,1→0)

문제에서 '할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것'이라고 했기에, 결국에는 이 문자가 연속되다가 바뀌는 부분에 대한 처리가 이루어져야 한다는 것이다.

이 부분을 상기하며 코드를 짜 보겠다.

def make_all_zero_or_one(string):
    if string[0] == '0':  # 0으로 시작한다면
        all_zero_cnt = 0  # 모두 0으로 만들고 싶을 때는 바꿀 필요가 없음
        all_one_cnt = 1  # 모두 1로 만들고 싶을 때는 바꿔줘야함 (바꾼다는 뜻이 아닌, 바꿔야한다는 뜻, 미리 계산한 것)
    elif string[0] == '1':  # 1로 시작한다면
        all_one_cnt = 0  # 모두 1로 만들고 싶을 때는 바꿀 필요가 없음
        all_zero_cnt = 1  # 모두 0으로 만들고 싶을 때는 바꿔줘야함

    for i in range(len(string) - 1):  # 실수 주의! : 인덱스가 i+1 까지 갈 것이기에 초장에 범위를 -1해줘야함
        if string[i] != string[i + 1]: # (중요!) 현재의 문자와 이어지는 문자가 다르다면
            if string[i + 1] == '0':  # 이전의 문자들은 모두 1이였다는 뜻
                all_one_cnt += 1  # 모두 1로 바꾸기 위해서 이 부분(i+1)은 0에서 1로 바뀌어야 된다라는 뜻, 미리 계산한 것
                # all_zero_cnt += 0 # 모두 0으로 바꾸기 위해서 이 부분은 이미 0 이므로 바꿀 필요가 없음
            elif string[i + 1] == '1':  # 이전의 문자들은 모두 0이였다는 뜻
                all_zero_cnt += 1  # 모두 0으로 바꾸기 위해서 이 부분(i+1)은 1에서 0로 바뀌어야 된다라는 뜻, 미리 계산한 것
                # all_one_cnt += 0  # 모두 1로 바꾸기 위해서 이 부분은 이미 1 이므로 바꿀 필요가 없음
    return min(all_zero_cnt, all_one_cnt)  # 둘 중의 최소값은 반환


print(make_all_zero_or_one('011110')) # 답: 1

이 코드에서 의문점이 생길 것이다.

왜 첫 글자가 0인지 1인지 판단할 때 cnt를 1 추가하는 것이지? 뒤에 이어지는 문자가 뭔지도 모르는데?

이 부분의 핵심은 결국 내가 바꿀 때 cnt를 +1 해주는 것이 아니라, 바뀌어야 하는 부분에서 미리 +1을 해준다는 것이다. 즉, 0011이라고 하면, 첫 인덱스에서 0이므로 1로 바꾼다고 가정하면, 미리 1에 대한 cnt를 추가해주고  0→1의 부분에서는 추가를 해주지 않는 것이다.

간단히 말하자면 '아 여기서부터 내가 문자를 바꾸어야 되는구나'라고 생각하고 미리 cnt를 추가한 다음에, 바뀌어야 하는 부분의 끝에서는 추가를 하지 않는 것이다.

---

지금 생각해보니깐 편하고자 코드를 이렇게 짰는데, 설명하자니 좀 복잡하게 짰다고 생각이 든다..

또, 이렇게 코드 설명을 적으니 내가 짠 코드가 어떻게 돌아가는 것인지 확실히 알게 되는 장점이 있는 것 같다.

이 문제에 대한 난이도는 내가 어렵게 접근해서 그런 건지 몰라도 중상 정도는 된다고 생각한다. 그런데 정답률이 50프로가 넘어가는 것을 보니 다른 사람들은 그 정도의 난이도로 느끼진 않을 것 같다.