[프로그래머스 | Lv2] 롤케이크 자르기 (Python)

 

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

프로그래머스

 

처음에 단순하게 푼 코드

차례대로 리스트를 나누면서 set으로 만들어 길이를 비교했다.

 

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

def solution(topping):
    answer = 0
    s = round(len(set(topping)) // 2)
    
    for i in range(s, len(topping)-s+1):
        if len(set(topping[:i])) == len(set(topping[i:])):
            answer += 1
        
    return answer

 

1번 빼고 전부 시간초과를 했고 (...) 

시간 줄여보겠다고 나름 정비를 거친 후 다시 시도했다.

매 시도마다 부분리스트를 만들고 그걸 또 집합으로 만드는 과정이 오래 걸린다고 판단하여

부분리스트, 부분집합을 미리 만들어주고 하나씩 빼고 더하면서 계산했다.

 

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

def solution(topping):
    answer = 0
    s = round(len(set(topping)) // 2)
    size = len(topping) - s*2

    t1 = topping[:-s]
    t2 = topping[-s:]

    s1 = set(t1)
    s2 = set(t2)

    for i in range(size):
        if len(s1) == len(s2):
            answer += 1

        p = t1.pop()
        if p not in t1:
            s1.remove(pop)
        s2.add(p)

    return answer

 

.. 4문제? 5문제? 빼고 또 전부 시간초과했다.

찾아보니 Counter를 이용하여 풀 수 있었다.

철수가 갖는 롤케이크는 딕셔너리(Counter)로 관리하고, 철수 동생이 갖는 롤케이크는 집합으로 관리한다.

마찬가지로 t1, t2를 미리 만들어주고 하나씩 빼고 더하면서 계산했다.

 

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

from collections import Counter

def solution(topping):
    answer = 0
    t1 = Counter(topping)
    t2 = set()
    
    for i in topping:
        t1[i] -= 1
        if t1[i] == 0:
            t1.pop(i)
        t2.add(i)
        
        if len(t1) == len(t2):
            answer += 1
    return answer

 

통과!!

😬