[Algorithm] 문자열 뒤집기

https://www.acmicpc.net/problem/1439

1439번: 뒤집기

 

 

이 문제 풀이의 핵심은 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 찾는 것이다.

그렇다면 어떻게 해야 뒤집어야 하는 0그룹의 개수와 1그룹의 개수를 구할 수 있을까?

 

필자는 이렇게 생각했다. 예시를 들어 생각해보자. 입력으로 '001101' 이 주어졌다고 치자. 입력값을 리스트에 넣고 리스트의 원소를 차례대로 이웃하는 원소와 비교를해서 값이 같다면 넘어가고, 값이 다르다면 해당하는 순서의 숫자에 대한 그룹의 수에 1을 더해준다. 이런식으로 반복하다 보면 0그룹의 수와 1그룹의 수를 구할 수 있고, 그 중 최솟값을 출력하도록 만들면 된다.

 

위의 아이디어를 가지고 코드를 다음과 같이 짜보았다.

 

data = list(map(int, input()))
cnt0 = 0
cnt1 = 0
result = 0

for i in range(0, len(data) - 1):
    if data[i] == data[i + 1]:
        if i == len(data) - 2:
            if data[i] == 0:
                cnt0 += 1
            else:
                cnt1 += 1
    else:
        if i == len(data) - 2:
            cnt0 += 1
            cnt1 += 1
        else:
            if data[i] == 0:
                cnt0 += 1
            else:
                cnt1 += 1

result = cnt1 if cnt0 > cnt1 else cnt0
print(result)

 

위 코드에서 아래와 같이 쓴 부분은 리스트의 마지막에서 2번째 원소에 대한 연산에서의 예외처리를 위해 집어넣은 코드이다. 하지만 문제점이 있다. 조건문을 남발해서 쓰다보니 가독성이 너무 떨어지고 코드가 지저분해 보인다.

 

if i == len(data) - 2

 

그래서 같은 아이디어지만 아래와 같이 좀 더 깔끔하게 코드를 써보았다.

 

data = list(input())
cnt0 = 0
cnt1 = 0

# 바뀌는 구간이 1번만 있는 경우를 고려. ex) 00100인 경우
if data[0] == '0':
    cnt1 += 1
else:
    cnt0 += 1

# 현재 문자가 다음 문자와 다를 때, 현재문자가 0이면 0에서 1로 바뀐다는 의미이므로 cnt0에 1을 더함
for i in range(len(data) - 1):
    if data[i] != data[i + 1]:
        if data[i] == '0':
            cnt0 += 1
        else:
            cnt1 += 1

print(min(cnt0, cnt1))

 

위 코드에서 아래의 부분이 맨 처음에 짰던 코드에서의 예외처리를 하는 부분이라고 생각하면 된다. 훨씬 코드가 간결해졌다.

# 바뀌는 구간이 1번만 있는 경우를 고려. ex) 00100인 경우
if data[0] == '0':
    cnt1 += 1
else:
    cnt0 += 1

 

그러나 더 간결한 코드가 있다. 아래의 코드는 알고리즘 스터디의 한 팀원이 작성한 코드이다.

 

s=input()
s=list(s)
cnt=0
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        cnt+=1 
print(cnt//2)

 

아이디어는 똑같지만 코드가 훨씬 간결하다.