프로그래머스 70129번 문제인 "이진 변환 반복하기" Lv.2을 파이썬으로 풀어보도록 하겠습니다.
[프로그래머스] 이진 변환 반복하기 Lv.2 - [파이썬/python]
💻 문제 설명
0과 1로 이루어진 어떤 문자열 s에 대한 이진 변환을 다음과 같이 정의합니다.
s의 모든 0을 제거합니다.s의 길이를 c라고 하면, s를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
예를 들어, s = "0111010"이라면, s에 이진 변환을 가하면 s = "0111010" -> "1111" -> "100" 이 됩니다.
0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 반환(return) 하도록 solution 함수를 완성해주세요.
🚨 제한사항
s의 길이는 1 이상 150,000 이하입니다.s에는 '1'이 최소 하나 이상 포함되어 있습니다.
!!!정답 주의!!!
🌟 소스 코드
def solution(s):
zero_count = 0 # 제거된 0의 개수를 저장할 변수
change_count = 0 # 이진 변환의 횟수를 저장할 변수
# s가 "1"이 될 때까지 반복
while s != "1":
# s에서 0의 개수를 세어 zero_count에 더하기
zero_count += s.count("0")
# s에서 1의 개수를 세고, 그 수를 2진법으로 변환한 후, 앞의 '0b'를 제거 후 s에 대입
s = bin(s.count("1"))[2:]
change_count += 1 # 이진 변환의 횟수를 증가
# 이진 변환의 횟수와 제거된 0의 개수를 리스트로 반환
return [change_count, zero_count]
⏱ 시간복잡도
위 코드의 시간 복잡도는 O(n)입니다.
- "0"과 "1" 개수 구하기: s.count("0")와 s.count("1")
문자열 s에서 특정 문자의 개수를 세는 데 O(n)의 시간이 소요됩니다.
- "1" 구하기 및 2진 변환: s = bin(s.count("1"))[2:]
문자열 s에서 1의 개수를 세고, 그 수를 2진법으로 변환한 후, 앞의 '0b’를 제거하는 데 O(n)의 시간이 소요됩니다.
따라서, 이 코드는 각 반복마다 O(n)의 시간이 소요되며, 문자열 s가 "1"이 될 때까지 이 과정을 반복합니다. 이는 입력 크기에 선형적으로 비례하는 시간 복잡도를 의미합니다.
🏳🌈 테스트 결과
728x90
'코딩테스트' 카테고리의 다른 글
| [프로그래머스] 피보나치 수 - Lv.2 (57) | 2023.10.28 |
|---|---|
| [프로그래머스] 짝지어 제거하기 - Lv.2 (55) | 2023.10.27 |
| [프로그래머스] 주사위 게임 3 - Lv.0 (52) | 2023.10.25 |
| [프로그래머스] 다음 큰 숫자 - Lv.2 (59) | 2023.10.21 |
| [프로그래머스] 겹치는 선분의 길이 - Lv.0 (51) | 2023.10.15 |