[그리디] 문자열 뒤집기

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

 

예를 들어 S 가 00011000 일때 모두 같게 하려면, 모두 1로 만들거나 모두 0으로 만들어야 한다.

먼저 모두 1로 만든다면 전체를 뒤집으면 1110011이 되고 그 후 4,5번째 문자를 뒤집으면 1111111 이 되어서 두번만에 모두 같은 숫자로 만들 수 있다. 다음 모두 0으로 만든다면 4,5번째 문자를 뒤집으면 00000000 이 되어서 한번만에 모두 같은 숫자로 만들 수 있고 정답은 1이 된다.

 

이 문제를 보고 처음 고민한 내용들이다. 복기를 위해 잘못된 생각도 그대로 적었다.

Q1) 4,5 번째 인덱스 1 만 0으로 뒤집으면 모두 같은 수라는걸 어떻게 알 수 있을까? 그리고 전부 0으로 뒤집는거와 전부 1로 뒤집는 것중 무엇으로 하는게 맞을지 어떻게 알 수 있을까?

for문으로 전체 순회해서 각각의 숫자를 다 알아야 가능하다.

Q2) for문을 돌면서 어떻게 파악을 할것인가?

단순히 0, 1 카운트를 높이는거 뿐만아니라 연속적인것도 체크 해야 된다.

 

이렇게 생각하다보니 더 복잡했다. 모두 1로 바꾸는게 나을지, 모두 0으로 바꾸는게 나을지 S 문자열을 보고 판단하는게 아니라 각각 수행 하고 그중 행동 최소 횟수를 답으로 하는 방향으로 가야했다.

 

그리고 고민됐던 포인트가 또 있었다. 문제에서 S 가 00011000 이고 모두 1로 만든다면, 먼저 전체를 뒤집어 1110011이 되게 하고 그 후에 4, 5번째 문자를 뒤집는 식으로 진행한다고 표현했다. 이걸 보고 안건드려도 되는 4,5번째 문자도 반드시 뒤집혀야 하는것으로 이해했고 한번 뒤집을 땐 전체에 다 영향을 준다고 생각했다. 그런데 두번째에서는 4,5 번째 문자만 뒤집는걸 보고 그건 또 아니므로 헷갈려졌다. 왜 처음에 1,2,3번째 문자만 1로 바꿔 11111000 이 되고 두번째로 6,7,8번째 문자를 1로 바꾼다고 표현하지 않았을까?

 

내가 작성한 코드는 아래와 같다. 연속적인것을 판단하기 위해 start 라는 flag 를 뒀다. 그리고 i+1 인덱스를 확인하는데 outOfIndex 문제가 발생할 수 있으므로 len(S) != i+1 이라는 조건을 추가로 줬다. 결국 값이 연속적이지 않은 상황에서 result를 증가시킴으로써 뒤집기 횟수를 표현했다(실제로 숫자를 바꾸는 행위는 불필요).

S = input()
def oneToZero():
	result = 0
	start = False	

	# 혹시 모를 방어로직
	if (len(S) == 1):
		return result
	else:
		for i in range(0, len(S)):
			if S[i] == '1' and start == False:
				result += 1

			if S[i] == '1' and len(S) != i+1 and S[i+1] == '1':
				start = True
			else:
				start = False
				
	return result

def zeroToOne():
	result = 0
	start = False	

	# 혹시 모를 방어로직
	if (len(S) == 1):
		return result
	else:
		for i in range(0, len(S)):
			if S[i] == '0' and start == False:
				result += 1

			if S[i] == '0' and len(S) != i+1 and S[i+1] == '0':
				start = True
			else:
				start = False

	return result

#print (oneToZero());
#print (zeroToOne());

print(min(oneToZero(), zeroToOne()))

 

책의 정답은 내가 작성한거보다 훨씬 간단하다. 여기도  i+1 인덱스를 확인하는데 나와는 달리 for문을 len(data)-1 까지만 돌게 하므로써 outOfIndex 문제를 피했다.

data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우
# 첫 번째 원소에 대해서 처리
if data[0] == '1':
	count0 += 1
else:
	count1 += 1
# 두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data)-1):
	if data[i] != data[i+1]:
		# 다음 수에서 1로 바뀌는 경우
		if data[i+1] == '1':
			count0 += 1
		# 다음 수에서 0으로 바뀌는 경우
		else:
			count1 += 1
print(min(count0, count1))

 

출처 : 이것이 코딩테스트다 나동빈 저

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