백준 #1439 뒤집기

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

예제 입력 1 복사

0001100

예제 출력 1 복사

1

예제 입력 2 복사

11111

예제 출력 2 복사

0

예제 입력 3 복사

00000001

예제 출력 3 복사

1

예제 입력 4 복사

11001100110011000001

예제 출력 4 복사

4

예제 입력 5 복사

11101101

예제 출력 5 복사

2

내 풀이:

# arr=list(input())

# arr=list(map(int,arr))

arr=list(map(int,input()))

a=0

b=0

for i in range(len(arr)-1):

    if arr[i]-arr[i+1]==-1:

        a+=1

    elif arr[i]-arr[i+1]==1:

        b+=1

    else: continue

   

if a<b:

    a=b

   

print(a)

   

#

정수로 이루어진 리스트에서 i번째 원소가 i+1번째 원소보다 1 큰 수인 경우의 횟수 = a

반대로 1 작은 횟수=b 라고 함.

그냥 0이고 1일 경우, 1이고 0일 경우 이렇게 하는 게 더 자연스럽고 간단했을 수 있겠다. 

아무튼 a랑 b중에 큰  값을 출력하면 됨.

 

#

그냥 1차이 나는 경우의 횟수를 세면 안 되는 이유는 예제 입력 3같은 경우가 있기 때문이다. 

 

#

첫줄= 정수들로 이루어진 리스트 만들기! 원래 두 줄로 썼었는데 한 줄로 써도 된다는 걸 알았다.

단 모든 원소가 한 자릿수면 이어서 써도 되지만 두자릿수 이상의 숫자가 섞여 있으면 input()뒤에 split도 붙여 줘야 할 것 같다.

 

 

c=input().count()

print(max(c('01'),c('10')))

#

같은 원리인데 최대한 간단하게 작성한 코드. 신기함.

 

arr=input()

a=0

for i in range(len(s)-1):

    if arr[i]!=arr[i+1]:

        a+=1

       

print((a+1)//2)

#

또 다른 방법

1이 연속되는 문자열과 0이 연속되는 문자열들을 각각 한 개의 블록으로 본다.

블록 종류가 0에서 1로, 1에서 0으로 바뀌는 시점을 구한다.(a)

다음 그 횟수에 +1을 해서 1블럭,0블럭이 번갈아가면서 나오는 전체 블럭의 개수를 구한다.

여기서 바꿔야 되는 블럭은 1블럭이나 0블럭 둘 중 하나니까 나누기 2한 몫만 보면 저절로 둘 중 더 적은 수의 블록을 최소 뒤집기만으로 바꿀 수 있는 횟수가 나온다. 

 

 

 

 

2024.10.01에 다시 푼 방법: 

뭔가 더 복잡해진 것 같기도..

str = input()

def mincount(str):
    count0 = 0
    count1 = 0
    if str[0] == '1':
        count1 += 1
    else: count0 += 1

    for i in range(1, len(str)):
        if str[i-1] != str[i]:
            if str[i] == '0':
                count0 += 1
            else: count1 += 1
        else: continue
    return min(count0, count1)

if len(str) ==1:
    print(0)    
else: print(mincount(str))

 

#

최소 행동 횟수는?
0 그룹의 개수와 1그룹의 개수 중 더 작은 걸 뒤집으면 됨. --> 더 작은 그룹의 개수를 출력하기

 

##

예외처리를 잘 해야 한다.. 작년에는 한 번에 푼 걸 지금은 몇 번 틀렸다. 
아이디어는 맞는 방향으로 가고 있었는데
1. str자체가 한 문자만으로 구성된 경우를 고려하지 않았고,
2. if문에 해당하지 않으면 반복문의 다음 구간으로 바로 넘어가게 하지도 않았다.