[Python] 프로그래머스 이진 변환 반복하기, 롤케이크 자르기

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

✅ 풀이

def solution(s):
    bin_count = 0
    zero_count = 0
    
    def s_to_bin(n):              # 2진법으로 변환하는 함수
        answer = ""
        while n != 0:
            answer += str(n%2)
            n = n//2
        return answer[::-1]
    
    while s != "1":       # s가 1이 될 때까지 반복
        bin_count += 1       # 이진 변환을 수행한 횟수
        zero_count += s.count("0")   # 변환 과정에서 제거된 모든 0의 갯수
        while "0" in s:               # 모든 0 제거
            s = s.replace("0", "")
        length = len(s)
        s = s_to_bin(length)      # 모든 0을 제거하고 난 뒤의 길이를 2진법으로 표현한 문자열로 바꿈
        
    return [bin_count, zero_count]

 

✅ 다른사람 풀이 1

def solution(s):
    bin_count = 0
    zero_count = 0
    
    while s != "1":       # s가 1이 될 때까지 반복
        bin_count += 1       # 이진 변환을 수행한 횟수
        zero_count += s.count("0")   # 변환 과정에서 제거된 모든 0의 갯수
        s = bin(s.count("1"))[2:]   # 1의 갯수를 세고, 해당 수를 이진수로 변환
        
    return [bin_count, zero_count]

 

- 각 이진수 변환 단계마다, 모든 0을 제거 한 다음의 문자열의 길이를 2진수로 바꾼다는거는 1의 갯수를 2진수로 바꾼다는것과 같다는 것을 활용하면 된다.

- 또한 Python에는 2진수 문자열로 바로 변환해주는 bin 함수가 있다. 단, 변환시 앞에 "0b"가 붙음에 유의하자

 

2. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/132265 

✅ 풀이

from collections import Counter

def solution(topping):
    answer = 0

    old = set()
    young = Counter(topping)
    
    for t in topping:
        old.add(t)
        young[t] -= 1
        
        if young[t] == 0:
            young.pop(t)    # del young[t]도 가능
            
        if len(old) == len(young):
            answer += 1
    
    return answer

 

이 문제는 topping의 길이 최대값이 1,000,000 이므로 반복문 안에서 매번 리스트 컴프리헨션을 통해 잘라서 비교하는것은 시간초과로 실패한다. 따라서 아래 아이디어를 활용해야 한다.

 

- 토핑의 갯수가 아닌 토핑의 "종류" 를 기준으로 하므로, 중복 제거 후 길이를 세기 위해 한쪽은 집합에 토핑을 업데이트 한다.

- 한쪽은, 처음에 토핑의 갯수를 딕셔너리로 저장한 뒤 반복문마다 토핑의 갯수를 -1 한다.

- 위와 같은 처리를 진행하면서 딕셔너리의 길이가 곧 토핑의 종류의 갯수가 되므로, 딕셔너리 길이와 집합의 길이가 일치하면 공평하므로 갯수를 1 증가시킨다.

 

예를들어 첫번째 예시와 같이 topping 배열이 [1, 2, 1, 3, 1, 4, 1, 2]일 경우

1) bro: [1] / young: {1: 3, 2: 2, 3: 1, 4:1 }

2) bro: [1, 2] / young: {1:3, 2: 1, 3: 1, 4:1 }

3) bro: [1, 2] / young: {1:2, 2: 1, 3: 1, 4:1 }

4) bro: [1, 2, 3] / young: {1:2, 2: 1, 3: 0, 4: 1} --> 여기서 3이 0이 되므로 3을 제거하면, young: {1: 2, 2: 1, 4: 1}

여기서 형이 [1, 2, 3] 토핑으로 갯수 3, 동생이 [1, 2, 4] 토핑으로 갯수 3이므로 공평하다. 따라서 이 때 + 1

 

오늘 배운 점

1. python의 2진수로 변환하는 함수는 bin 이고, 앞에 "0b"가 붙기때문에 2진수로 변환하는 문자열만 가져오려면 [2:]를 붙여서 가져오자