[Programmers] 롤케이크 자르기 -Javascript 번외편<왜 이게 안돼?>

INDEX

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

프로그래머스

 

Solution

 

철수와 동생이 서로 다른 토핑의 개수가 동일하게 롤케이크를 자를 수 있는 경우의 수를 구하는 문제입니다.

동생이 우선 롤케이크 전부다를 가진다고 가정한 다음 한 조각씩 철수에게 줄 때 철수가 가지고 있지 않던 토핑이면 철수의 토핑개수 +1, 동생이 한 조각을 줌으로써 동생이 가지고 있던 토핑의 개수가 동이 나면 동생의 토핑개수 -1 하면 됩니다.

 

이를 코드로 풀면 다음과 같습니다.

function solution(topping) {
    let answer = 0;
    let dongSangMap = {}; 
    let dongSangToppingCnt = 0;
    //우선 동생이 가지고 있는 토핑 종류의 수를 계산합니다.
    for(let i=0; i<topping.length; i++){
        if(dongSangMap[topping[i]]) dongSangMap[topping[i]] += 1;
        else {
            dongSangMap[topping[i]] = 1;
            dongSangToppingCnt++;
        }
    }
    
    //한 조각씩 옮기면서 철수의 토핑 종류의 수를 계산합니다.
    let chulsuMap = {}
    let chulsuToppingCnt = 0;
    while(topping.length){
        const top = topping.shift();
        if(!chulsuMap[top]){
            chulsuToppingCnt++;
            chulsuMap[top] = 1;
        }
        dongSangMap[top]--;
        if(dongSangMap[top] === 0) dongSangToppingCnt--;
        if(chulsuToppingCnt === dongSangToppingCnt) answer++;
    }
    
    return answer;
}

 

오잉? O(n) 의 시간복잡도를 가진 알고리즘인데 시간초과가 났습니다. 물론 반복문 두 개를 돌렸으니 따지고 보면 2 * O(n)인 건데, 그렇다고 해서 이게 시간초과가 나다니.. 

계속 고민해서 반복문을 한 번만 쓰는 방법을 생각해 봐도 떠오르지가 않았습니다. 우선 동생이 토핑을 몇 개나 다른 걸 가지고 있는지 알아야 하는데...

그래서 다른 분의 풀이를 참고했는데 정말 신기한걸 발견했습니다.

이 분도 Javascript 를 사용했고 푼 알고리즘도 완전히 동일한데 이 분은 통과를 했더군요.

function solution(topping) {
    let answer = 0;
    const topping1 = {} , topping2 = {} 
    let topping1Count = 0,topping2Count = 0

    // topping2에 전부 세팅 
    topping.forEach((element)=>{
        if(topping2[element] === undefined){
            topping2[element] = 1
            topping2Count++
        }
        else{
            topping2[element]++
        }
    })

    // 순서대로 자르기 진행하면서 topping2에서 topping들 topping1으로 옮기기 
    topping.forEach((element)=>{
        if(topping2[element]-1 === 0){
            topping2Count--
            delete topping2[element]
        }
        else{
            topping2[element]--
        }

        if(topping1[element] === undefined){
            topping1Count++
            topping1[element] = 1
        }
        else{
            topping1[element]++
        }

        answer += (topping1Count===topping2Count)
    })

    return answer;
}

참고 : https://school.programmers.co.kr/questions/52663

프로그래머스

 

저의 코드와 이 분의 코드 차이점을 분석했더니 다른 점은 반복문이였습니다.

 

저는 for문과 while을 사용했고 이 분은 forEach를 사용했더군요. 저도 수정해 봤습니다.

function solution(topping) {
    let answer = 0;
    let dongSangMap = {}; 
    let dongSangToppingCnt = 0;
    //우선 동생이 가지고 있는 토핑 종류의 수를 계산합니다.
    topping.forEach((item)=>{
        if(dongSangMap[item]) dongSangMap[item] += 1;
        else {
            dongSangMap[item] = 1;
            dongSangToppingCnt++;
        }
    })
    
    let chulsuMap = {}
    let chulsuToppingCnt = 0;
    topping.forEach((item)=>{
        if(!chulsuMap[item]){
            chulsuToppingCnt++;
            chulsuMap[item] = 1;
        }
        dongSangMap[item]--;
        if(dongSangMap[item] === 0) dongSangToppingCnt--;
        if(chulsuToppingCnt === dongSangToppingCnt) answer++;
    })
    
    return answer;
}

그랬더니 

forEach문만 사용

 

잉? 정말 신기했습니다.. 반복문을 forEach 로만 바꿨는데 소요시간을 단축시켰습니다. 그럴 일 없다 싶어 이번엔 반복문을 for 문으로만 바꿨습니다.

for 문만 사용

forEach 보다 미세하게 더 좋은 성과를 냈습니다. 여러 자료를 찾아보니 배열의 원소 개수가 많아질수록 for loop의 성능이 제일 우수하다고 합니다..

https://blog.bitsrc.io/measuring-performance-of-different-javascript-loop-types-c0 e9 b1 d193 ed

Measuring Performance of Different JavaScript Loop Types

 

평소에 while 문이 사용하기에 편해서 자주 애용하곤 했는데 이제는 신중하게 사용해야겠군요..