문제 설명
0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.
- x의 모든 0을 제거합니다.
- 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'이 최소 하나 이상 포함되어 있습니다.
입출력 예
| s | result |
|---|---|
"110010101001" | [3, 8] |
"01110" | [3, 3] |
"1111111" | [4, 1] |
풀이
def solution(s):
sum_of_remove_zero = 0
count_of_binary_transformation = 0
while True:
if s == '1':
break
num_of_zero = s.count('0')
sum_of_remove_zero += num_of_zero
s = '1' * (len(s) - num_of_zero)
s = format(len(s), 'b')
count_of_binary_transformation += 1
return [count_of_binary_transformation, sum_of_remove_zero]해결 과정
문자열 내에서 '0'의 개수를 구하기
문자열에서 '0'을 제거하는 replace 보다는 새로운 문자열을 만드는 것이 더 편리할 것 같아 '0'의 개수를 구하는 방식으로 접근했다.
해당 값을 구해 sum_of_remove_zero에 더한다. 이는 문제에서 요구한 "변환 과정에서 제거된 모든 0의 개수"를 저장하기 위해서다.
'0'을 전부 제거하기 때문에 문자열은 모두 '1'로 이루어진다. 그렇다면 파이썬의 문자열 반복(* 연산자)을 사용할 수 있다.
반복되는 횟수는 "전체 길이에서 '0'의 개수를 뺀 값'이다.
s의 길이 값을 이진 변환하기
이렇게 변환된 s의 길이를 이진 변환해야 한다. 파이썬에서는 bin 내장 함수나 format 내장 함수가 이를 지원해주고 있기 때문에 둘 중 하나를 사용하면 된다.
다만, bin은 이진 문자열이 반환될 때 앞에 이진수임을 알리는 '0b'가 붙어서 반환된다. 문제를 풀 때 이는 필요가 없으니 반환할 때 포함되지 않도록 해주는 format을 사용했다.
이진 변환 횟수 저장하기
문제에서 "이진 변환의 횟수"도 반환해야 한다고 명시했기에 이를 count_of_binary_transformation에 저장한다.
다른 사람의 풀이
def solution(s):
a, b = 0, 0
while s != '1':
a += 1
num = s.count('1')
b += len(s) - num
s = bin(num)[2:]
return [a, b]반드시 '0'의 개수에 포커스를 맞출 필요는 없었다. 사실 s에서 '0'을 제거한다는 것은 결국 s에 있던 '1'의 숫자만큼 '1'이 반복되는 문자열로 변환된다는 뜻이다.
"제거한 '0'의 개수"는 '1'의 개수를 전체 길이에서 빼면 구할 수 있는 값이고, '1'의 개수를 구했으니 이진 변환 코드가 더 짧아질 수밖에 없다.
