손가락놀이터

문제 후기

해당 문제를 처음 접하고 문자를 list형태로 변환하여 해결하려 했습니다. 완성한 결과 배열이 계속해서 for문을 통해 탐색을 하여 시간초과가 나왔습니다. 이후 변환을 하지 않고 문자열상태에서 count와 +-를 활용하여 해결했습니다.

문자열로 나오는 경우 먼저 문자열로 해결할 수 있는지 확인하거나 시간을 확인한 이후 배열로 해결해야겠습니다.

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 c를 2진법으로 표현한 문자열로 바꿉니다.

예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 1이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 '1'이 최소 하나 이상 포함되어 있습니다.

코드

def solution(s):

    change_transform = 0    # 변환 횟수
    remove_zero = 0         # 0 제거 횟수
    sentence = s            # input 값. 알고리즘 활용 문자

    # 2진수가 3자리 이상인 경우에 반복문 진행.
    while len(sentence) > 2:

        new_sentence = ""   # 변환한 문자
        chk_one = sentence.count("1")   # 1의 갯수, 다음 계산하는 이진수
        remove_zero += sentence.count("0")  # 제거한 0을 더해줌.
        len_next = chk_one  # 1의 갯수, 아래 while문에서 활용하는 변수

        # 1의 갯수를 다시 2진수로 변환. 
        while len_next > 1:

            new_sentence = str(len_next % 2) + new_sentence
            len_next = len_next // 2
        
        # 2진수가 3자리 이상인 경우 1을 추가.
        if chk_one != 2 and chk_one != 3:
            new_sentence = "1" + new_sentence
            change_transform += 1
        
        # 2진수가 "11" 인 경우 3번 변환과 0을 한번 제거
        elif chk_one == 3:
            change_transform += 3
            remove_zero += 1
            return [change_transform, remove_zero]
        
        # 2진수가 "10"인 경우 2번 변환과 0을 한번 제거
        else:
            change_transform += 2
            remove_zero += 1
            return [change_transform, remove_zero]

        sentence = new_sentence
    # 2진수가 "1"로 끝난 경우
    return [change_transform, remove_zero]