문자열 뒤집기

 

문제

0, 1로만 이루어진 문자열을 뒤집어 모든 숫자를 같게 만들어야한다.

연속된 하나 이상의 숫자를 뒤집을 수 있다. 1->0 or 0->1

이 때, 최소한으로 뒤집어 모두 같은 문자열을 만들어라.

 

 

유형파악

"최소한"이라는 말이 나왔기에 합리적으로 그리디 알고리즘을 의심한다.

 

 

아이디어

"결과는 항상 00000 처럼 0으로만 이루어져 있거나 11111 처럼 1로만 이루어진다."

 

0001001010101110 가 있다고 가정할때,

모두 1로 만들기 위해서는 6번 뒤집는다.

모두 0으로 만들기 위해서는 5번 뒤집는다.

 

그냥 머리속에 있는 것을 만들어보려고 한다.

결과는 항상 1로만 이루어져 있거나 0으로 이루어질 것이다.

1개 이상의 연속된 0의 수와 1의 수를 구하여 더 작은 집합의 수를 출력한다.

 

 

정당성

결과는 항상 정해져 있다

0으로만 이루어져있거나 1로만 이루어져 있다.

뒤집는 방식에는 0만을 뒤집기, 1만을 뒤집기, 0,1 둘다 뒤집기가 있다.

0 or 1만 뒤집는 것은 앞에서 고려했다.

둘 중 하나를 랜덤으로 뒤집는 것을 생각해보면

길이가 가장 긴 연속된 집합 뒤집기를 할것이고

예시로 0000101100111 이 있다고 가정해보면

-> 1111101100111

-> 000001100111

-> 1111111100111

-> 00000000111

-> 11111111111111

횟수가 너무 많다.

그리고 적당히 골라서 뒤집는 경우를 생각해보면 항상 1만을 뒤집거나 0만을 뒤집는 경우와 동일하다.

 

" 또한 직관적으로 생각해봐도 한가지만 파는게 연산횟수가 적다. 쉽게 생각하고 여러가지 너무 많은 경우의 수를 고려하는 것은 가끔은 직관적인 사고에 방해가 되는 것 같다. " 

 

 

 

구현

1. 숫자를 확인해가며 전에 뽑은 숫자와 지금 숫자를 비교해가며 연속된 집합인지를 판단

2. 적은 집합 출력

 

 

 

코드

input = input("입력 : ")
result = []
index0 = 0
index1 = 0
for i in range(len(input)):
    
    if i == 0:
        result.append(input[i])
        continue

    if result[-1] == input[i]:
        result.append(input[i])
    else:
        if int(result[-1]) == 0:
            index0 += 1
            result = [input[i]]
        else:
            index1 += 1   
            result = [input[i]]
            
if result[0] == 0:
    index0 += 1
else:
    index1 += 1
print(index0)
print(index1)

 

시간 복잡도

문자열의 길이는 최대 100만이다. 즉 100만개의 숫자가 나열될 수 있음을 의미한다.

100만개의 숫자를 for문을 돌린다.

for문은 기본적으로 시간복잡도가 O(N)이다. 제한시간 또한 2초이다. 1초안에 돌아갈 것으로 예상한다.

자세히 살펴보면 O(상수*N)이다 하지만 시간복잡도는 계수를 고려하지 않고 뒤에 상수 또한 고려하지 않는다.

파이썬은 평균 5000만번의 계산이 가능하다.

 

 

공간복잡도

처음에 코드를 작성할때는 group0, group1로 만들어 거기에 그룹들을 넣고 마지막에 수가 작은 것을 구하는 방식으로 했다.

이는 비효율적이였다. 100만개의 데이터를 int로 바꾸어 하나당 4바이트 씩 넣는다고 가정하고 400만바이트이고 4MB이다. 용량이 128MB이므로 충분하지만 4MB만큼 데이터를 쓰는 것은 비효울적이다. 따라서 상수로 계산을 하였고 용량은 데이터를 저장하는 것 말고는 사용되지 않는다.