프로그래머스 이진 변환 반복하기 (DFS 파이썬 풀이)

• 문제

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

프로그래머스

 

 

• 소스코드(DFS)

binary_cnt = 0

def dfs(s, cnt):
    global binary_cnt

    if s == "1":
        return [cnt, binary_cnt]

    cnt += 1
    binary_cnt += s.count("0") 
    s = bin(s.count("1"))[2:]  

    return dfs(s, cnt)

def solution(s):
    return dfs(s, 0)

 

 

• 해설

이 문제도 DFS 공부를 위해 재귀적으로 풀어본 문제이다 이문제는 주어진 이진수의 0을 제거하고 만들어진 수를 다시 이진화 하여 0을 몇번 없애는 지 구하는 문제이다.

 

글러벌 변수로 0을 몇번 없앴는지 변수로 설정하고 dfs를 들어와 수행 할때마다 cnt를 증가시켜 구하는 식으로 하였다.

 

이문제의 핵심은 count 함수와 bin을 사용하여 간단하게 구현한 부분이다. bin을 사용할 때 주의 할 점은 bin을 사용하면 앞에 "0b" 가 생기므로 슬라이싱을 사용하여 필요한 부분만 사용하게 하는 것 과 DFS의 종료조건이 중요하다. 문제에 "1" 이 될때 까지 라고 하여 dfs의 수행 cnt 와 글로벌 변수 binary_cnt 를 리턴 하여 문제를 풀었다.