[프로그래머스] 이진 변환 반복하기 - Lv.2

프로그래머스 70129번 문제인 "이진 변환 반복하기" Lv.2을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] 이진 변환 반복하기 Lv.2 - [파이썬/python]

 

 

프로그래머스-이진-변환-반복하기

---

💻 문제 설명

 

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

 

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

 

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

 

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/70129

프로그래머스

---

🚨 제한사항

 

• 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"이 될 때까지 이 과정을 반복합니다. 이는 입력 크기에 선형적으로 비례하는 시간 복잡도를 의미합니다.

---

🏳‍🌈 테스트 결과

 

프로그래머스-이진-변환-반복하기-상태

 

프로그래머스-이진-변환-반복하기-테스트-결과