[Programmers] 롤케이크 자르기 (Lv 2, Python)

[ 개요 ]

토핑을 나눌 수 있는 방법은 전체 토핑이 있을 때, 토핑을 순차적으로 제외해가며 제외된 토핑과 남아있는 토핑을 비교하는 경우로 생각할 수 있음

[ 학습 내용 ]

이 문제에서 defaultdic와 counter을 사용하였을 때, 실행결과 속도는 defaultdict가 2배 빨랐음
※ collections

from collections import defaultdict

##### useage
dicList = defaultdict(list)
dicSet = defaultdict(set)

### 다음 list를 defaultdict에 list형태로 추가할 때 다음의 예시가 있음
s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]

1) list
for k, v in s:
	d[k].append(v)			# basic
    d.setdefault(k, []).append(v)	# setdefault
 
2) set
for k, v in s:
	d[k].add(v)			# basic
	d.setdefault(k, []).add(v)	# setdefault
    
### setdefault를 활용하는 경우 더 빠름(공식문서 피셜)

### key-value 형태로 매핑되며, 결과값은 다음과 같음
list : [('blue', [2, 4]), ('red', [1])]
set : [('blue', {2, 4}), ('red', {1})]

from collections import Counter

##### useage
1) create
c = Counter()                           # a new, empty counter
c = Counter('gallahad')                 # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
c = Counter(cats=4, dogs=8)             # a new counter from keyword args

2) search
c = Counter(['eggs', 'ham'])
c['bacon']				
#result	: 0

3) delete
c = Counter(['sausage'])
del c['sausage']		# not work 	: c['sausage'] = 0

3-1) clear
c.clear()

3) iterator
c = Counter(a=4, b=2, c=0, d=-2)	# if value < 0, ignore
sorted(c.elements())
#result	: ['a', 'a', 'a', 'a', 'b', 'b']

4) subtract with Counter
c = Counter(a=4, b=2, c=0, d=-2)
d = Counter(a=1, b=2, c=3, d=4)
c.subtract(d)
c
#result	: Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

5) total
c = Counter(a=10, b=5, c=0)
c.total()
#result	: 15

[ 소스 코드 ]

※ defaultdict

from collections import defaultdict

def solution(topping):
    first, second = defaultdict(int), set()
    count = 0
    for i in topping:
        first[i] = first[i] + 1
    for i in topping:
        first[i] = first[i] - 1
        if first[i] == 0:
            del first[i]
        second.add(i)
        if len(second) == len(first):
            count = count + 1
        if len(second) > len(first):
            break
    return count

※ Counter

from collections import Counter

def solution(topping):
    first, second = Counter(), Counter()
    answer = 0
    for n in topping:
        first[n] = first[n] + 1
    for n in topping:
        first[n] = first[n] - 1
        if first[n] == 0:
            del first[n]
        second[n] = second[n] + 1
        if len(first) == len(second):
            answer = answer + 1
            
    return answer