[이코테] 그리디 - 문자열 뒤집기 with 파이썬

1. 문제

• 백준1439 와 같은 문제 https://www.acmicpc.net/problem/1439
• 0,1 숫자로된 연속된 문자열이 들어온다.
• 연속으로 연결된 숫자를 뒤집는다.
• 뒤집는 것은 0 -> 1, 1 -> 0
• 연결된 숫자를 뒤집는 것이 한 동작이고
• 행동의 최소 회수를 구하는 프로그램을 만들라.

입력 조건

• 0,1 숫자로된 연속된 문자열

출력 조건

• 뒤집는 행동의 최소 회수

입력 예시

0001100

출력 예시

1

2. 아이디어

• 규칙을 찾아보았다. 0이던 1이던 연결된 것을 한 덩어리로 생각
  • 00011000 , 3덩어리 -> 1번
  • 00110011 , 4덩어리 -> 2번
  • 0011001100, 5덩어리 -> 2번
  • 001100110011, 6덩어리 -> 3번
  • 00110011001100, 7덩어리 -> 3번
• 관계는 덩어리 수의 몫
• 덩어리 수 : i, i+1 같은지 확인, 다르면 cnt 상승
• 답은 덩어리수 // 2

3-1. 예제 코드 1 (my version)

# 입력
nums = list(map(int, input()))
# 덩어리 수 확인 , 덩어리수는 바뀌는 횟수 + 1
cnt = 1
for i in range(len(nums)-1):
    if nums[i] != nums[i+1]:  # 직전, 직후가 다르면, 덩어리 수 증가
        cnt += 1

print(cnt//2)

3-2. 예제 코드 2 (💡저자 version)

• 저자는 경우의 수를 모두 1로 바꾸는 경우, 모두 0으로 바꾸는 경우 두가지로 생각하고,
• 두 경우에 대해서 각각 if 문으로 count를 한 후,
• 그 두 경우 중 더 작은 것을 구하는 방법을 사용 했다.

# 입력 
nums = list(map(int, input()))

# count 초기화
count_0 = 0  # 모두 0으로 바꾸는 경우
count_1 = 0  # 모두 1로 바꾸는 경우

## 연산의 기준은 바꿀 횟수 
# 첫번째 값 
if nums[0] == 1: # 1이면 count_0 상승
    count_0 += 1
else :
    count_1 += 1
    
# 두번째값 이후
for i in range(len(nums)-1):
    if nums[i] != nums[i+1]:  # 덩어리가 바뀌면
        if nums[i+1] == 1:    # 1이면 , 0으로 바꾸는 횟수 증가 
            count_0 += 1
            
        else : 
            count_1 += 1      # 0이면, 1로 바꾸는 횟수 증가
            
print(min(count_0, count_1))  # 둘 중 최소값

4. 배운점

• 모두 0으로 바꾸고, 모두 1로 바꾸는 것을 동시에 행하고, 최소값을 구한다는 저자와 같은 생각은 못했다.
• 덩어리가 바뀐다는 것이 i, i+1를 확인하는 것임을 다시 한번 상기할 수 있었다.

참조

• 이것이 취업을 위한 코딩테스트다. with 파이썬