[이취코] 알고리즘 유형별 기출문제: 그리디 - 3. 문자열 뒤집기 (Python)

3. 문자열 뒤집기

문제

• 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 할 때, 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집기란 0을 1로 1을 0으로 만드는 것을 말한다.
• 문자열 S가 주어졌을 때 다솜이가 해야 하는 행동의 최소 횟수를 출력하시오.

예시

• 예를 들어 S = 0001100일 때
  • 전체를 뒤집으면 1110011이 됨
  • 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어 두번만에 모두 같은 숫자로 만들 수 있음
  • 하지만 처음부터 4번째 문자부터 5번째 문자까지 뒤집으면 한 번에 0000000이 되어 모두 같은 숫자로 만들 수 있음

입출력 조건

• 입력: 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어짐. S의 길이는 100만 보다 작음
• 출력: 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력

풀이

1) 내 풀이

0과 1중 더 많은 걸로 통일해야 함

010101010 → 1을 0으로 뒤집어야 함

반례: 011100110 → 1이 더 많지만 0보다 1을 2번 뒤집는 게 더 빠름

→ 연속한 0과 1을 하나로 뭉치자!

011100110을 01010으로 만들고 0과 1중 더 적은 것을 뒤집는 것!

for문으로 연속한 0과 1을 하나로 뭉치고 더 적은 수를 더 많은 수로 바꾸는 횟수 세기

101 → 1번

0101 → 2번

10101 → 2번

→ 반 나누고 나머지 버리기

더 적은 숫자의 개수만큼 하면 되지만 그게 나누기 2랑 똑같음

시간 복잡도: O(n)

공간 복잡도: O(k) - 최대 O(n) (01010101~ 길이가 100만인 문자열)

# 그리디 - 3. 문자열 뒤집기
S = input()
parse = S[0]
for crnt in S[1:]:
    if crnt != parse[-1]:
        parse += crnt
print(int(len(parse)/2))

2) 교재에 나온 풀이

전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중 더 적은 횟수를 갖는 경우를 계산하기

리스트 맨 앞부터 0→1 또는 1→0의 횟수 세기

for문으로 숫자가 바뀌는 횟수 센다는 아이디어는 내 아이디어와 동일

숫자가 바뀌는 횟수만 세느냐, 연속한 숫자를 하나로 압축한 후 횟수를 세느냐에 대한 차이

시간 복잡도: O(n)

공간 복잡도: O(1)

S = input()
count0 = count1 = 0
if data[0] == '1':
	count0 += 1
else:
	count1 += 1
for i in range(len(data)-1):
	if data[i] != data[i+1]:
		if data[i+1] == '1': # 0 -> 1
			count0 += 1
		else: # 1 -> 0
			count1 += 1 
print(min(count0, count1))