[Python] 프로그래머스 롤케이크 자르기 풀이

문제 확인

프로그래머스

 

나의 풀이

• 가짓수를 동일하게 케이크를 분리해야 한다.
• 앞 케이크 분리 시, 뒷 케이크의 일부 성분이 없어져 가짓수가 바뀔 수 있다는 것을 주의해야 한다.
• 이 생각을 안하고 이분 탐색으로 접근해서 풀었고, 결국 스스로 푸는데는 실패했다.
• 아래는 다른 사람의 코드를 보고 이해한 내용이다.

 

각 케이크 가짓수를 따로 저장해서 관리

• 우선 각 케이크의 idx 별 가짓수를 pt1_cnt, pt2_cnt에 저장한다.
• 모두 저장이 끝나면 pt1_cnt[i]와 pt2_cnt[i + 1] 이 동일한 지 확인하고, 그 수를 세면 된다.

def solution(topping):
    # idx 별 케이크 가짓수 보관
    pt1_cnt, pt2_cnt = [], []
    # 나눈 케이크의 가짓수 확인
    pt1_unique, pt2_unique = set(), set()
    # pt1 케이크 확인
    for t in topping:
        pt1_unique.add(t)
        pt1_cnt.append(len(pt1_unique))
    # pt2 케이크 학인
    for t in topping[::-1]:
        pt2_unique.add(t)
        pt2_cnt.append(len(pt2_unique))
    # 비교를 위해서 역순으로 되돌리기
    pt2_cnt = pt2_cnt[::-1]
    return sum([1 for i in range(len(pt1_cnt) - 1) if pt1_cnt[i] == pt2_cnt[i + 1]])

롤케이크 자르기

 

• 위 코드와 유사한 풀이 방법으로, Counter와 set을 사용해서도 풀 수 있다.
• set은 pt1, dic을 pt2로 생각하면 된다. 

from collections import Counter

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

 

[프로그래머스] Lv.2 롤케이크 자르기 | Python - velog