[2주차공통] 문자열 뒤집기

0과 1로만 이루어진 문자열 S가 있다.

이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 

 

할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 0을 1로, 1을 0으로 바꾸는 것이다.

 

예를 들어 S=0001100일 때

 

1트 : 전체를 뒤집으면 1110011이 된다.

2트 : 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 된다.

 

하지만 처음부터,

처음부터 4번째부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 된다. 

 

---

초기 접근

 

우선, 0을 1로 바꿀지, 1을 0으로 바꿀지 둘 중 하나를 선택할 수 있어야 한다. 

연속된 수를 뒤집는 것이 1회 실행이므로, 1의 연속된 세트는 몇개인지, 0의 연속된 세트는 몇개인지 계산한 후

연속된 세트의 개수가 더 적은 쪽의 세트 개수를 출력한다. 

 

연속된 세트 수는 문자열의 처음부터 각 수가 1인지 0인지 판단해가면서 세트 개수를 셀 수 있다. 

 

또는, i 위치의 수가 i-1과 다른 경우, 하나의 세트가 바뀌는 지점이다. 이 지점을 찾고,

이때 i-1 위치에 있는 값에 따라 어떤 세트count변수 를 증가시킬지 정할 수 있다.

 

또는 last변수를 두어 이전 수와 같았는지 아닌지 비교할 수 있다.

last변수를 초기에 무엇으로 정해야할지 관건인데, 첫번째 인덱스로 만나게 되는 수는 last값과 무조건

달라야한다. 그래야 첫번째 인덱스의 수부터 세트count변수를 유효하게 작동시킬 수 있기 때문이다.

 

따라서 last값을 0도 1도 아닌 2로 두었다. 

 

list=list(int(input()))

set0count=0
set1count=0

last=2

for i in list:
    if i==0&&last!=0:
        set0count+=1
    else if i==1&&last!=1:
        set1count+=1
    else:
        pass
    last=i
    
print(min(set0count,set1count))

 

 

파이썬 문법을 다 틀리게 썼다는 것을 알앗다..

 

1. 입력을 사용해 정수로 구성된 리스트 만들기

int(input())는 한 자리 숫자를 입력받을 때는 잘 작동하지만, 여러 자릿수를 입력하고 이를 리스트로 변환하려는 경우에는 적합하지 않다. 왜냐하면 int(input())는 전체 입력을 하나의 정수로 처리하기 때문이다.

# 예시
input()           # "10101"을 문자열로 입력받음
list(input())     # ['1', '0', '1', '0', '1'] -> 문자열 리스트
list(map(int, input()))  # [1, 0, 1, 0, 1] -> 정수 리스트
int(input())      # 10101 -> 하나의 정수

 

2. else if 대신 파이썬에서는 elif를 쓴다.

 

3. &&대신 파이썬에서는 and를 쓴다.

 

모두 수정한 코드는 아래와같다,

 

list = list(map(int, input()))  # input 값을 int 리스트로 변환

set0count = 0
set1count = 0

last = 2  # 처음에는 0, 1이 아닌 값으로 설정

for i in list:
    if i == 0 and last != 0:
        set0count += 1
    elif i == 1 and last != 1:  # 'else if'는 'elif'로 수정
        set1count += 1
    last = i

print(min(set0count, set1count))

---

이 문제가 그리디 알고리즘과 어떻게 관련있는지 잘 모르겠다.

지금 당장 좋은 것을 선택한다는 알고리즘을 쓴것같지는 않다. 오히려 단순 구현에 더 비슷한 것 같다고 생각한다.