[연습문제] 롤케이크 자르기- Python / Javascript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

 

[문제 간단 요약]

1. 롤케이크에 여러 종류의 토핑이 얹어져 잇음

2. 롤케이크를 자를 때, 왼쪽과 오른쪽의 토핑 종류 수가 같게하는 지점의 수 반환하는 문

[문제 해결 방안] - 항목배열 방식

1. 왼쪽, 오른쪽 토핑의 수를 관리

2. 전체 토핑이 오른쪽에 있다고 가정하고 배열 카운트

3. 왼쪽으로 하나씩 토핑을 옮기면서 토핑 갯수 비교

 

[문제 해결 코드 - python]

def solution(topping):
    answer = 0
    topping_l = [0]*(max(topping)+1)
    topping_r = [0]*(max(topping)+1)
    l_count = 0
    r_count = 0
    for topp in topping:
        topping_r[topp] += 1
        if topping_r[topp] == 1:
            r_count+=1
    for topp in topping:
        topping_r[topp] -= 1
        topping_l[topp] += 1
        if topping_r[topp] == 0:
            r_count-=1
        if topping_l[topp] == 1:
            l_count+=1
        if r_count == l_count:
            answer+=1
    return answer

 

[문제 해결 코드 - javascript]

function solution(topping) {
    let answer = 0;
    let r = Array(10001).fill(0) 
    let l = Array(10001).fill(0)
    let r_c = 0
    let l_c = 0
    for (let i = 0; i < topping.length; i++) {
        r[topping[i]] += 1
        if (r[topping[i]] === 1) {
           r_c += 1 
        }
    }
    for (let i = 0; i < topping.length; i++) {
        r[topping[i]] -= 1
        l[topping[i]] += 1
        if (r[topping[i]] === 0) {
            r_c -= 1
        }
        if (l[topping[i]] === 1) {
            l_c += 1
        }
        if (l_c === r_c) {
            answer += 1
        } else if (l_c > r_c) {
            return answer
        }
    }
    return answer;
}

 

[코드 비교 요약]

• 항목배열 방식 vs set/Counter 방식

시간 복잡도	O(N)	O(N)
공간 복잡도	O(M)	O(N)
상수 시간 연산	✅	❌
메모리 제한 우수	✅	❌
코드 간결성	❌	✅

 

[문제 해결 코드 - python] - set/Counter 방식

from collections import Counter
def solution(topping):
    left = set()
    right = Counter(topping)
    answer = 0
    for t in topping:
        left.add(t)
        right[t] -= 1
        if right[t] == 0:
            del right[t]
        if len(left) == len(right):
            answer += 1
    return answer