Programmers / 롤케이크 자르기 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 롤케이크 자르기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

def solution(topping):
    answer = 0
    
    for i in range(len(topping)):
        set1 = set(topping[:i])
        set2 = set(topping[i:])
        if len(set1) == len(set2):
            answer += 1
        
    return answer

 

당연하게 시간 복잡도 O(N)이라고 생각하고 풀었지만 리스트 슬라이싱은 시간 복잡도는 k가([i:j] 일때 k = i + j -1)된다.

그래서 위 풀이는 시간 복잡도가 O(N)이 아닌 O(N^2)가 되었다.

 

from collections import Counter

def solution(topping):
    answer = 0

    cnt1 = Counter(topping)
    cnt2 = {}
    
    for i in range(len(topping)):
        if topping[i] in cnt2:
            cnt2[topping[i]] += 1
        else:
            cnt2[topping[i]] = 1
        cnt1[topping[i]] -= 1
        
        if cnt1[topping[i]] == 0:
            del cnt1[topping[i]]
        
        if len(cnt2) == len(cnt1):
            answer += 1

    return answer

 

from collections import Counter를 사용해보라는 조언을 받고 딕셔너리를 사용하여 cnt2에 하나 주고 cnt1에 하나 받고 하면서 풀었더니 답이 나왔다.

---

※ 알아야 할 것

 

파이썬의 라이브러리를 적극적으로 사용할 것

그리고 from collections import Counter에서 Counter는 리스트에서 중복되는 원소의 개수를 딕셔너리로 받아준다.