Homework 2
0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다.
할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다.
뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
(소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.)
"0001100" # 주어진 문자열 예시이 문자열을 모두 0 혹은 1로 만들기 위해서는 두가지 방법이 있습니다.
- 모두 0으로 만드는 방법
1) 4번째 원소와 5번째 원소를 잡고 뒤집으면?0000000이 됩니다.
문자열을 순서대로 탐색하다보면
뒤집는 시점은 바로 0에서 1로 변할 때 뒤집어야 하는 걸 감지할 수 있습니다!
- 모두 1으로 만드는 방법
1) 1번째 원소와 3번째 원소를 잡고 뒤집으면?1111100이 됩니다.
2) 6번째 원소와 7번째 원소를 잡고 뒤집으면?1111111이 됩니다.
문자열을 순서대로 탐색하다보면
뒤집는 시점은 1에서 0으로 변할 때 뒤집어야 하는 걸 감지할 수 있습니다.
즉, 모두 0으로 만드는 방법이 1회이므로 최소 횟수입니다!
나의 풀이
def find_count_to_turn_out_to_all_zero_or_all_one(string):
overlap = 0
count = 0
for i in range(1, len(string)):
if string[i-1] == string[i]:
continue
else: # string[i-1] != string[i]
count += 1
if string[i] != string[-1]: # 맨 마지막은 중복이 생길 수 없으므로.
overlap += 1
return count-overlap-
생각한 과정 : 우선 문자열의 처음부터 끝까지 순차적으로 돌면서
0->1또는1->0이렇게 바뀌는 포인트에 집중하였다. 바뀌는 부분마다count를 1씩 추가하려니 다시 원래 숫자로 돌아올 때 중복해서count에 1씩 추가되는 것을 방지하기 위해overlap이라는 변수를 선언하여, 맨 마지막을 제외(중복이 생길 수 없으므로)하고 1씩 증가시킨 후 마지막에count에서 빼주는 방식으로 구하였다. -
해당 풀이의 문제점 : 결과적으로 문자열 내의 숫자가 모두
0 또는 1이 되는 상황을 모두 고려했어야 했는데, 처음 문자를 기준으로만 생각하다보니 첫 문자에 따라 최솟값이 나오지 않을 상황이 생길 수도 있다는 문제가 있었다.
해답
def find_count_to_turn_out_to_all_zero_or_all_one(string):
count_to_all_zero = 0
count_to_all_one = 0
# 결과의 값이 모두 0이되냐 1이 되냐를 나누기위해 위의 두 변수 선언
if string[0] == '0':
count_to_all_one += 1
elif string[0] == '1':
count_to_all_zero += 1
for i in range(len(string) - 1):
if string[i] != string[i + 1]:
if string[i + 1] == '0':
count_to_all_one += 1
if string[i + 1] == '1':
count_to_all_zero += 1
return min(count_to_all_one, count_to_all_zero)- 내 풀이와 다른점 :
1)count변수를 두 개 선언하여 결과가 모두 0이 될 경우와 1이 될 경우를 나누어 생각함.
2) 나는 변경 포인트마다count를 추가했다면, 후자의 방법은count_to_all_zero,count_to_all_one두 개로 놓고 바뀌는 다음 숫자가 0이냐 1이냐에 따라 나누어 횟수를 추가했으므로 중복이 발생하는 문제가 없다.
