[프로그래머스] 132265: 롤케이크 자르기 | 집합(set),counter

[프로그래머스] 132265: 롤케이크 자르기

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

프로그래머스

 

---

[python] 문제풀이

1. 초기설정

• 철수가 처음에 모든 토핑을 가지고 시작 ->  cheolsu 딕셔너리에 모든 토핑을 종류별로 수량을 저장
• 동생의 토핑을 기록할 bro 딕셔너리를 빈 상태로 시작
• topping 리스트를 deque로 변환하여 맨 앞에서부터 토핑을 하나씩 철수에게서 동생에게 넘김

2. 토핑 이동

• topping에서 하나씩 popleft를 하면서 cheolsu 에서 해당 토핑수 줄임.
• 만약 토핑 수가 0이 되면 해당 토핑을 cheolsu에서 삭제
• bro에 해당 토핑이 없으면 새로 추가하고, 이미 있으면 수량을 1 증가

3. 결과 출력

• 두 딕셔너리의 길이가 같다면 철수와 동생이 공평하게 나눈 것이므로 answer에 1을 더함
• 동생의 토핑 종류가 철수보다 많아지거나 topping deque에 남은 토핑이 없으면 while 루프를 종료

 

 

 

 

from collections import deque

def solution(topping):
    cheolsu = {}
    for t in topping:
        if t in cheolsu:
            cheolsu[t] += 1
        else:
            cheolsu[t] = 1
    
    # 동생의 토핑 딕셔너리 초기화
    bro = {}
    topping = deque(topping)
    answer = 0

    # 토핑을 하나씩 옮겨가면서 확인
    while topping:
        # 철수의 토핑에서 하나빼서
        t = topping.popleft()  # t에 저장
        cheolsu[t] -= 1 #해당 토핑 갯수 줄이기
        if cheolsu[t] == 0:
            del cheolsu[t] #개수가 0이 되면 딕셔너리에서 해당 토핑 제거

        # 동생의 토핑에 추가
        if t in bro:
            bro[t] += 1 #이미 해당 토핑이 있다면 개수 증가
        else:
            bro[t] = 1 #없었다면 1 새로 추가

        # 공평하게 나눠진 경우를 체크
        if len(cheolsu) == len(bro):
            answer += 1
        
        # 동생의 토핑 종류가 철수보다 많아지면 종료
        if len(bro) > len(cheolsu):
            break

    return answer

근데 좀 느림........................... 아마 개수를 일일히 다 세서 그런듯 싶음

개수를 고려하지 않고 종류만 관리하면 코드를  최적화할 수 있을 것 같다

 

+) 코드 최적화

from collections import Counter

def solution(topping):
    answer = 0
    bro = set()             # 동생이 가진 토핑 종류
    cheolsu = Counter(topping)  # 전체 토핑의 종류와 개수

    for t in topping:
        bro.add(t)         # 현재 토핑을 동생의 집합에 추가
        cheolsu[t] -= 1    # 해당 토핑의 개수를 1 감소시킴

        if cheolsu[t] == 0: # 만약 해당 토핑의 개수가 0이 되면
            del cheolsu[t]  # 해당 토핑을 cheolsu에서 삭제
            
        # 공평하게 나눌 수 있는 경우 체크
        if len(bro) == len(cheolsu):
            answer += 1

    return answer

집합 set ()

• 딕셔너리에서 값을 제거한 key와 비슷한 원리
• {} 중괄호로 값을 구분
• 순서대로 저장되지 않음
• 중복된 값은 한번만 저장

 

 

엥 근데 counter 쓰니까 더 느려짐 ;;

Counter는 내부적으로 해시 테이블을 사용하여 각 요소와 그 개수를 저장하게 됨

키 -  값 쌍으로 데이터 저장하기 때문에 각 토핑마다 추가적인 메모리 소비하게됨.

-> 메모리 사용 많아짐

 

 

 

[python] counter