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

bee·2023년 4월 12일
0

코딩테스트

목록 보기
4/16
post-thumbnail

🔎 문제 설명

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'이 최소 하나 이상 포함되어 있습니다.





💡 풀이 아이디어
1) 제거할 '0'의 개수(zero)를 세고 '0' 제거한다.
2) c를 측정(='1' 개수 카운팅)하고 2진법으로 표현한다.
3) 1)과 2)의 과정까지를 1 iteration으로 간주하고, 이진변환 횟수(cnt) 1회 추가와 제거된 0의 개수(d)에 zero를 누적한다.

## 내 풀이
def solution(s):
    answer = []
    cnt = 0 # 이진변환 횟수
    d = 0 # 제거된 '0' 개수
    
    while True:
        zero = s.count('0') # 제거할 0개수
        s = s.strip('0') # (1) '0' 제거
        c = s.count('1') # 남은 s의 길이
        s = format(c, 'b') # (2) c를 2진법 표현
        
        cnt += 1 # 이진변환 횟수 카운팅
        d += zero # 제거된 0의 개수 누적
        
        if s == '1' :
            break
        
    answer.append(cnt)
    answer.append(d)
    return answer

print(solution('01110'))

[3, 3]



예제의 동작 원리는 아래 그림과 같다.

풀면서 내가 착각했던 부분은 cnt += 1의 위치였는데, s == 1이 되지 않더라도 이미 첫 시작부터 1회차로 간주하기 때문에 if문 뒤가 아닌 앞으로 와야 하는 것이 맞다.


더 간결하고 효율적인 풀이가 있어서 정리해두고 공부하고자 한다.
(헷갈릴 것 같아서 변수명은 내가 사용했던 변수명으로 대체하였다.)

## 다른 풀이
def solution(s):
	cnt, d = 0, 0
    
    while s != '1' :
    	cnt += 1 # 이진변환 회차 카운팅
        c = s.count('1') # 문자열 s 내 '1'의 개수
        d += len(s) - c # 제거된 '0'의 개수
        s = bin(c)[2:] # 슬라이싱으로 접두어 제거
        
    return [cnt, d]

확실히 다른 사람들 풀이와 내 풀이를 비교해보니까 내 코드가 얼마나 비효율적이고 코드 짤 때 1차원적으로 생각하는지 보인다. 다른 사람들 풀이를 많이 찾아보면서 공부해야할 것 같다.

profile
벌집처럼 밀도있게 차곡차곡 쌓아나가는중

0개의 댓글