[프로그래머스 | 파이썬 / 자바스크립트] 롤케이크 자르기(연습문제/ level 2)

문제

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

프로그래머스

 

 

🐍파이썬

from collections import Counter 
def solution(topping):
    answer = 0
    toppingDic = Counter(topping)	#사전 형식으로 (원소:원소갯수)가 저장된다.
    toppingSet = set()
    for i in topping:
        toppingDic[i] -= 1	#사전에서는 -1로 토핑종류를 1감소시킨다.
        toppingSet.add(i)	#set에는 토핑종류를 1증가시킨다. 중복제거를 위해 set을 사용한다.
        if toppingDic[i] == 0:	#사전의 토핑종류가 0인 원소는 제거한다.
            toppingDic.pop(i)
        if len(toppingDic) == len(toppingSet):	#사전길이와 set길이를 비교해 토핑종류갯수가 같은 경우 asnwer+=1
               answer += 1
    return answer

✔ collections 모듈의 Counter를 이용한다.

 

 

🐥자바스크립트

❌ 시간초과 실패 코드

function solution(topping) {
    var answer = 0;
    let toppingDic = {}
    topping.forEach((i)=>{
        i in toppingDic === false ? toppingDic[i] = 1 : toppingDic[i] += 1;
    })
    let toppingSet = new Set();
    for(let i of topping){
        toppingDic[i] -= 1;
        toppingSet.add(i);
        if(toppingDic[i] === 0){
            delete toppingDic[i]
        }
        if(Object.keys(toppingDic).length === toppingSet.size){
            answer += 1;
        }
    }
    return answer;
}

👉 파이썬과 동일하게 사전에 모든 원소를 넣고 하나씩 빼고 더하며 답을 구하는 방식을 사용하려 했는데 시간초과가 발생했다. 이후 자바스크립트 풀이답안을 보고 delete를 이용해 사전 원소를 제거하는 대신, dicLen을 이용해 사전의 길이만 따로 구하는 식으로 문제를 풀었더니 정답으로 인정되었다. delete하고 매번 사전 길이를 구하는 데 시간이 많이 소요되는 것 같다.

function solution(topping) {
    var answer = 0;
    let toppingDic = {}
    
    //topping의 모든 원소 갯수를 세서 dic에 저장
    topping.forEach((i) => {    
        i in toppingDic === false ? toppingDic[i] = 1 : toppingDic[i] += 1;
    })
    // toppingDic = { '1': 4, '2': 2, '3': 1, '4': 1 }
    
    let toppingSet = new Set(); //중복제거를 위한 set, 형 토핑 종류 카운트
    let dicLen = Object.keys(toppingDic).length //dic의 길이를 카운트, 동생 토핑 종류 카운트
    
    //topping리스트를 처음부터 끝까지 돌며 dic에서는 원소를 하나 빼고 set에는 더한다.
    for(let i of topping){
        toppingDic[i] -= 1;
        toppingSet.add(i);
        //사전의 값이 0이 된 경우 토핑종류를 -1시키기 위해 dicLen을 1감소시켜준다.
        if(toppingDic[i] === 0){
            dicLen -= 1;
        }
        //dicLen과 set의 길이가 같은 경우 동일한 토핑갯수이므로 answer+=1 
        if(dicLen === toppingSet.size){
            answer += 1;
        }
    }
    return answer;
}

 

 

다른 풀이 방법

function solution(topping) {
    const a = new Set()
    const b = {}
    let answer = 0;
    let check = 0
    
    for (let i = 0; i < topping.length; i++) {        
        if (b[topping[i]]) {
            b[topping[i]]++
        } else {
            b[topping[i]] = 1
            check++            
        }
    }

    for (let i = 0; i < topping.length; i++) {
        a.add(topping[i])
        b[topping[i]]--

        if (!b[topping[i]]) check--
        if (a.size === check) answer++
    }
    return answer;
}