문제 - 문자열 뒤집기

 

# 문제 

Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다. 
할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 
뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 

주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

 

 

# 예시 

input : "0001100"

이 문자열을 모두 0 혹은 1로 만들기 위해서는 두가지 방법이 있습니다.

1. 모두 0으로 만드는 방법
1) 4번째 원소와 5번째 원소를 잡고 뒤집으면? `0000000` 이 됩니다.

문자열을 순서대로 탐색하다보면
뒤집는 시점은 바로 0에서 1로 변할 때 뒤집어야 하는 걸 감지할 수 있습니다!

2. 모두 1으로 만드는 방법
1) 1번째 원소와 3번째 원소를 잡고 뒤집으면? `1111100` 이 됩니다. 
2) 6번째 원소와 7번째 원소를 잡고 뒤집으면? `1111111` 이 됩니다.

문자열을 순서대로 탐색하다보면
뒤집는 시점은 1에서 0으로 변할 때 뒤집어야 하는 걸 감지할 수 있습니다.

즉, 모두 0으로 만드는 방법이 1회이므로 최소 횟수입니다!

 

# 나의 풀이법 

문제 이해를 위해 여러 가지 예시를 갖고 파악을 해보았다. 
우선 같은 문자열을 만들려면 0으로 하든 1로하든 2가지 방법이 있다. 

1) "0010001010" 의 경우 
	1-1) 0으로 만드는 경우 
        0010001010 -> 0000001010  1번
        0000001010 -> 0000000010  2번
        0000000010 -> 0000000000  3번 
        
    1-2) 1로 만드는 경우
        0010001010 -> 1110001010 1반
        1110001010 -> 1111111010 2번
        1111111010 -> 1111111110 3번
        1111111110 -> 1111111111 4번
        
2) "111110000011" 인 경우 

	2-1) 0으로 만드는 경우 
        111110000011 -> 000000000011  1번
        000000000011 -> 000000000000  2번
        
    2-2) 1로 만드는 경우
        111110000011 -> 1111111111111 1번
        
3) "111000" 인 경우 

	2-1) 0으로 만드는 경우 
        111000 -> 000000  1번
        
    2-2) 1로 만드는 경우
        111000 -> 111111 1번
  
  
경우의 수를 나열하고 보니 0으로 만드나 1로 만드나 둘의 관계는 같던지 1개가 차이가 나며 
만드는 횟수는 숫자변화가 몇개 일어났느지에 따라 달려졌다. 

"00001110010001" 의 경우 
	0이 4
    1이 3
    0이 2
    1이 1
    0이 3
    1이 1 
    
    의 순서를 가져갔고 각 리스트의 숫자만큼 숫자가 변경되었다. 
    
    리스트로 표현한다면 [4, 3, 2, 1, 3, 1]
    
    이를 1로 바꿀려고 하면 첫번째 수가 0으므로 첫번째부터 바꿔야한다. 즉
    1, 3, 5 순서대로 뒤집으면 되므로 총 갯수는 3개가 나오고 
    
    이를 0으로 바꿀려고 하면 두번째 수가 1이므로 두번째부터 바꿔야한다. 
    즉, 2, 4, 6 순서대로 뒤집으며 되므로 총 개숫는 3개가 나온다
    
    따라서 리스트를 순회하며 같은 숫자만큼 묶어서 리스트로 표현을 했고 
    
    각 리스트의 원소의 짝수, 홀수는 각각 같은 숫자이므로 리스트의 총 원소 갯수는 
    
    1의 묶음 갯수 + 0의 묶음 갯수이므로 묶음 갯수만큼 뒤집으면 되기때문에 반으로 나누어 
    
    최소 횟수를 구한다.

 

 

# 전체 코드

input = "00011100"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    order = []	# 숫자 파악을 우한 빈리스트
    curr = string[0]	# 처음 시작이 저장
    cnt = 0
    for i, char in enumerate(string):
        if curr == char:	# 이전 숫자랑 같다면 
            cnt += 1		# 갯수를 세고
        else:
            curr = char		# 다르면 리스트에 추가하고 
            order.append(cnt)	# 현재 비교할 숫자를 바꿈 0->1 / 1->0
            cnt = 1
    order.append(cnt)
    return len(order)//2	# 전체 리스트 갯수의 절반을 반환
    						# 전체리스트 = [3, 3, 2]


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

 

해당 문제는 처음 봤을 때는 막막했다. 어떻게 뒤집을 지 기준을 잡는게 어려웠고 전체 뒤집기도 할 수 있어서 이를 항상 고려 해야되나..? 싶어서 고려하는 방법을 찾으려다가 너무 어려워서 무작정 예시를 들어서 정리해 가봤다. 

 

정리를 하다보니 다음 과 같은 방법을 찾아 냈고 이것이 우연인지 맞는 방법 인지는 모르겠으나 암튼 품..! 우연인 것같아서 모범답안을 확인 해보았다. 

 

 

# 답안 코드

 

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string): 
    count_to_all_zero = 0	# 1으로 뒤집을 때 카운트
    count_to_all_one = 0	# 0으로 뒤집을 때 카운트

    if string[0] == '0':	# 처음 시작 확인
        count_to_all_one += 1 	# 첫시작이 0 이면 1로 바꾸는 횟수 +1
    elif string[0] == '1':		# 첫시작이 1 이면 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':	# 앞의 숫자가 0이라면 1으로 바꾸는 횟수 +1
                count_to_all_one += 1
            if string[i + 1] == '1':	# 앞의 숫자가 1이라면 0으로 바꾸는 횟수 +1
                count_to_all_zero += 1

    return min(count_to_all_one, count_to_all_zero)	# 둘중 최솟값 반환


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

 

답안 코드가 좀 더 문제 를 푸는 알고리즘에 가깝다는 걸 느꼈다. 

 

리스트를 순회하면서 자기자신인 원소와 그 다음 원소를 비교하면서 진행하는 것이 더 깔끔하게 만들어지는 것 같고 

 

문제에서 요구한 방법 대로 알고리즘이 짜여진 것같다. 

 

반면에 나는 문제를 재해석 하여 푼 느낌이 강하게 들었다. 

 

앞으로는 문제의 방향대로 푸는 연습을 해야겠다. 

 

---