[그리디 7] 문자열 뒤집기
연속된 하나 이상의 수를 뒤집어서 전부 0 또는 1로 변경해야 하는데 최소로 뒤집어야 한다. 주어진 숫자에서 연속된 0의 집합의 개수 또는 연속된 1의 집합의 개수가 더 적은 것을 뒤집어야 최소의 뒤집기로 0 또는 1로 만들 수 있다. 따라서 탐욕법이고 그리디 방법이다.
미니 예제 1
1. 문제 설명하기.
S가 0001100 인 경우이다.
Step 1. S에서 연속된 0의 집합의 개수와 연속된 1의 집합의 개수를 구한다. 0001100 인 경우에는 000 | 11 | 00 이기 때문에, 연속된 0의 집합의 개수는 2개이고 연속된 1의 집합의 개수는 1개이다.
Step 2. 초기값을 만들어준다. (여기서 초기값은 현재 수의 바로 앞 숫자를 의미한다.)
Step 2-1. 초기값이 0인 경우에는 1이 나올 때 연속된 0의 집합의 개수에 +1 처리한다. 그리고 초기값을 재설정한다.
Step 2-2. 초기값이 1인 경우에는 0이 나올 때 연속된 1의 집합의 개수에 +1 처리한다. 그리고 초기값을 재설정한다.
Step 3. 2단계까지 진행하면 마지막 집합의 개수는 세어주지 않는다. 따라서 마지막 집합이 어떤 것인지 확인하고 +1 처리한다.
2. 문제 풀이하기.
# 미니 예제 1 : S=0001100 인 경우
S="0001100"
count_one=0
count_zero=0
## Step 1.
init=int(S[0])
## Step 2.
for num in S[1:]:
num=int(num)
if init==0:
if num==init:
init=num
continue
count_zero+=1
init=num
else:
if num==init:
init=num
continue
count_one+=1
init=num
## Step 3.
if (int(S[-1])==1) and (int(S[-2])==1):
count_one+=1
if (int(S[-1])==0) and (int(S[-2])==0):
count_zero+=1
if count_zero<=count_one:
result=count_zero
result=count_one
print(result)최적의 일반화
1. 문제 설명하기.
Step 1. S에서 연속된 0의 집합의 개수와 연속된 1의 집합의 개수를 구한다. 0001100 인 경우에는 000 | 11 | 00 이기 때문에, 연속된 0의 집합의 개수는 2개이고 연속된 1의 집합의 개수는 1개이다.
Step 2. 초기값을 만들어준다. (여기서 초기값은 현재 수의 바로 앞 숫자를 의미한다.)
Step 2-1. 초기값이 0인 경우에는 1이 나올 때 연속된 0의 집합의 개수에 +1 처리한다. 그리고 초기값을 재설정한다.
Step 2-2. 초기값이 1인 경우에는 0이 나올 때 연속된 1의 집합의 개수에 +1 처리한다. 그리고 초기값을 재설정한다.
Step 3. 2단계까지 진행하면 마지막 집합의 개수는 세어주지 않는다. 따라서 마지막 집합이 어떤 것인지 확인하고 +1 처리한다.
2. 문제 풀이하기.
# Check!
S="1011001001"
count_one=0
count_zero=0
## Step 1.
init=int(S[0])
## Step 2.
for num in S[1:]:
num=int(num)
if init==0:
if num==init:
init=num
continue
count_zero+=1
init=num
else:
if num==init:
init=num
continue
count_one+=1
init=num
## Step 3.
if (int(S[-1])==1) and (int(S[-2])==1):
count_one+=1
if (int(S[-1])==0) and (int(S[-2])==0):
count_zero+=1
if count_zero<=count_one:
result=count_zero
result=count_one
print(result) # 3개가 나와야 한다.# 최적의 일반화
S=input()
count_one=0
count_zero=0
init=int(S[0])
for num in S[1:]:
num=int(num)
if init==0:
if num==init:
init=num
continue
count_zero+=1
init=num
else:
if num==init:
init=num
continue
count_one+=1
init=num
if (int(S[-1])==1) and (int(S[-2])==1):
count_one+=1
if (int(S[-1])==0) and (int(S[-2])==0):
count_zero+=1
if count_zero<=count_one:
result=count_zero
result=count_one
print(result)3. 책에 나와있는 최적의 일반화
접근 방식은 동일하다. 하지만 나처럼 계속 초기값을 재설정하는 것보다 인덱스를 이용하는 것이 더 직관적으로 보기 좋다.
| 기준 | 나의 풀이 | 책의 풀이 |
|---|---|---|
| 바로 앞, 현재 숫자 | 초기값 재설정하기. | 인덱스 이용하기. |
Step 1. 첫 번째 값 (즉 현재의 숫자)를 지정해주기. 1인 경우 count_one에 +1 처리하고, 0인 경우 count_zero에 +1 처리한다.
🌠 Step 2. 인덱스를 이용하여 현재의 수와 그 전의 수를 표기할 것이다. (현재 숫자의 인덱스) = (앞에 있는 숫자의 인덱스) + 1 를 이용하면 된다. 따라서 그 전의 숫자의 인덱스로 반복문을 돌려준다.
🌠 현재의 숫자와 앞의 숫자가 다른 경우 현재의 수가 1이면 count_zero에 +1 처리하고, 0인 경우 count_one에 +1 처리한다.
Step 3. 가장 적은 횟수가 최소로 뒤집어서 전부 0 또는 1로 만드는 횟수이다.
# 책에 나와있는 풀이
S=input()
count_zero=0
count_one=0
## 1. 첫 번째 값에 따라 count_zero에 더해줄지 count_one에 더해줄지 고민하기.
if S[0]=="1":
count_one+=1
else:
count_zero+=1
## 2. 전 숫자의 인덱스 까지 돌리고 (전 숫자의 인덱스 + 1) = 현재 숫자의 인덱스임을 이용한다.
for idx in range(len(S)-1):
if S[idx] != S[idx+1]: # 현재와 전 숫자가 다른 경우
if S[idx+1] == "1": # 현재의 수가 1이면
count_zero+=1 # count_zero에 +1
else: # 현재의 수가 0이면
count_one+=1 # count_one에 +1
## 3. 최소인 값이 최소의 횟수로 뒤집는 것이다.
print(min(count_zero, count_one)) 