[이코테 Ch11-3] 문자열 뒤집기 (그리디)

👩🏻‍💻문제설명

[이코테 Ch11-3] 문자열 뒤집기 (그리디)

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다.
예를 들어 S = 0001100일 때는 다음과 같습니다.

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

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

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

입력조건

• 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다. S의 길이는 100만보다 작습니다.

출력조건

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

입력예시
0001100

출력예시
1

✍️Idea Sketch

문제 요약

0과 1 숫자로 이뤄진 문자열 S
모든 숫자를 전부 같게 만들기
뒤집는 행동의 최소 횟수를 구하라

0) 0001100
1) 전체 뒤집기 1110011
2) 일부 뒤집기 1111111
=> 총 2회

0) 0001100
1) 일부 뒤집기 0000000
=> 총 1회

시간복잡도

O(n) --> S의 길이는 100만보다 작음 --> 시간 초과X

for문으로 문자열 S를 순차탐색하므로 O(n)이다. S의 길이는 100만보다 작아 1억에 못 미치므로 시간초과 걱정은 없다.

알고리즘 : 그리디

문제에서 주어진 대로 구현하지 않는다. 문제에서는 전체를 뒤집는 경우/일부를 뒤집는 경우를 보여주었지만 이를 고려하지 않는다. 창의력, 즉 문제를 풀기 위한 아이디어를 떠올리는 능력이 필요한 문제이다.

1. 연속된 0과 연속된 1의 개수를 구한다.
2. 둘 중에 더 작은 개수를 출력한다.

✍️내 소스코드

1. 연속된 0과 연속된 1의 개수를 구한다.
   • cnt 배열의 인덱스 0번째에는 연속된 0의 개수를 저장하고, 인덱스 1번째에는 연속된 1의 개수를 저장한다.
   • 문자 x가 이전값 tmp와 다른 경우 (연속하지 않은 경우) cnt와 tmp를 갱신한다.
2. 둘 중에 더 작은 개수를 출력한다.

  import sys
  si = sys.stdin.readline

  s = si().rstrip()
  cnt = [0, 0]
  tmp = -1

  for x in map(int, s):
    if x != tmp:
      cnt[x] += 1
      tmp = x

  print(min(cnt))