BAEKJOON #1439) 뒤집기 (python)

    반응형

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

     

     

    1439번: 뒤집기

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

    www.acmicpc.net

    알고리즘 분류: 그리디 알고리즘

     

    💡코드 + 풀이

    #1

    s = list(input())
    cnt0 = 0
    cnt1 = 0
    
    if s[0] == '0':
        cnt0 += 1
    else:
        cnt1 += 1
    
    for i in range(len(s)-1):
        if s[i] != s[i+1]:
            if s[i]=='0':
                cnt1 += 1
            else:
                cnt0 += 1
        else:
            continue
            
    print(min(cnt0, cnt1))
    • 0으로 바뀌는 구간을 카운트하는 변수 cnt0와 1로 바뀌는 구간을 카운트하는 변수 cnt1을 각각 생성한다.
    • 우선, 첫번째 문자만 확인 후, 0이면 cnt0에 1을, 1이면 cnt1에 1을 더해준다. (바뀌는 구간이 1번만 있을 때와 바뀌는 구간이 아예 없을 때를 구분하기 위해서이다.)
      • s cnt0 cnt1 최소 행동 (정답)
        00 1 0 0
        01 1 1 1
    • 그리고 for문으로 전체 문자열을 돌면서 현재 문자가 다음 문자와 다를 때, 현재 문자가 0이면 0에서 1로 바뀐다는 뜻이므로 cnt1에 1을 더하고, 반대의 경우에는 cnt0에 1을 더한다.
    • 최소 행동을 구하는 것이 문제의 정답이므로 cnt0과 cnt1 중 작은 수를 출력한다.

     

     

     

    #2

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

    2번 풀이는 1번 풀이에서 규칙을 발견한 것을 적용하여 풀이한 것이다.

    연속된 문자가 몇개 있는지는 관계없이 0에서 1로, 또는 1에서 0으로 바뀌는 구간이 몇개인지가 이 문제를 해결하는 데에서 중요하다.

    s 바뀌는 구간 최소 행동 (정답)
    0 또는 1 0 0
    01 또는 10 1 1
    010 또는 101 2 1
    0101 또는 1010 3 2
    01010 또는 10101 4 2
    010101 또는 101010 5 3
    0101010 또는 1010101 6 3

    이렇게 연속된 문자는 생략한 채, 나타날 수 있는 경우를 차례대로 써보면 규칙이 잘 보인다.

    최소 행동 = (바뀌는 구간 + 1) // 2로 나타날 수 있다.

    이렇게 보여지는 규칙을 사용하면 위의 1번 풀이처럼 0에서 1로 1에서 0으로 바뀌는 구간을 따로 구분할 필요가 없다!

     

    반응형

    댓글