[프로그래머스] Level2 - 롤케이크 자르기(Javascript)

프로그래머스

▶ 문제 요약

1. 철수와 동생은 케이크의 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 나누어진 것으로 판단

2. 철수랑 동생은 동일한 토핑의 개수를 맛봐야 한다. 

3. 공평하게 자르는 방법의 수를 찾아라.

▶ 실패 코드

function set(number) {
  let set = new Set(number);
  return set;  

} 

function solution(topping) {
    let answer = 0;
    let left = 0;
    let right = topping.length;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        let leftTopping = topping.slice(0, mid), rightTopping = topping.slice(mid, topping.length);
        
        let leftSet = set(leftTopping).size, rightSet = set(rightTopping).size;
        
        if (leftSet == rightSet) {
            answer++;
        } 
        
        if (leftSet < rightSet) {
            left++;
        } else if (leftSet > rightSet) {
            right--;
        }
        
        
    }
    
    console.log(answer)
    
    
}

▶ 실패한 이유

• 이 코드가 통과할 줄 알았는데 시간이 엄청 오래 걸린다. 이유 주어진 배열의 길이는 최대 1,000,000이다. 내 코드에서 Set()함수와 슬라이싱 하는 부분은 각각 O(n)의 시간복잡도를 가진다. 
• 최선의 경우: O(n) 루프가 한 번만 실행되는 경우
• 최악의 경우: O(n^2) 루프가 n 번 실행되고, 각 루프에서 슬라이싱과 집합 계산이 최악의 시간복잡도를 가지는 경우)
• 입력값의 길이가 최대 1,000,000인 경우, 최악의 시간복잡도는 O(1,000,000 ^ 2)이므로 매우 비효율적인 알고리즘이다.
• 그니까 시간초과가 난다. 문제를 제대로 안 읽나? 반성의 시간이 필요하다... 

 

▶ 정답 코드

function solution(topping) {
    let answer = 0;
    // Map() 함수 생성
    let freq = new Map();
    // Set() 함수 생성
    let leftFreq = new Set();
    
    // Map에 일단 입력값을 다 넣어준다. 
    for (const t of topping) {
        freq.set(t, (freq.get(t) || 0) + 1);
    }
	
    // 기존에 Map()에 담긴 것들은 하나씩 지워주고
    // 반면에 Set()에는 하나씩 담겨주면서 
    // 공평하게 맞춘다.
    for (const t of topping) {
        freq.set(t, (freq.get(t)-1);
        leftFreq.add(t);
        
        // 만약에 원소의 값이 없으면 삭제
        if (freq.get(t) === 0) {
            freq.delete(t);
        }
        
        // 만약에 Map()함수의 사이즈와 Set()함수의 사이즈가 같으면 +1
        if (freq.size === leftFreg.size) {
        	answer += 1;
        }
        
    }
    return answer;




}

 

▶ 풀이 과정

1. 이 코드는 Map()함수와 Set()함수를 사용했다. 이유는 밑에서 더 설명하겠다.

 

2. 일단 입력값을 for of 반복문을 사용해서 Map에 set메서드를 사용해서 넣는다. 그 뒤에 get()메서드를 사용해서 Map()에 들어있는 t가 있는지를 확인하고 혹은 없을 경우 0을 사용한다. 즉 현재 개수를 반환하거나 없는 경우 0을 반환한다. 현재 개수 +1 또는 0 + 1의 값을Map()에 넣어주면 값과 값의 개수가 잘 들어간다.

 

3. 다시 for of 반복문을 사용하는데 여기서 왜 Map()함수와 Set()함수를 사용한지가 나온다. 이해를 돕기 위해 topping = [1, 2, 1, 3, 1, 4, 1, 2]를 돌려보겠다.

Map(4) { 1 => 3, 2 => 2, 3 => 1, 4 => 1 } Set(1) { 1 }
Map(4) { 1 => 3, 2 => 1, 3 => 1, 4 => 1 } Set(2) { 1, 2 }
Map(4) { 1 => 2, 2 => 1, 3 => 1, 4 => 1 } Set(2) { 1, 2 }
Map(4) { 1 => 2, 2 => 1, 3 => 0, 4 => 1 } Set(3) { 1, 2, 3 }
Map(3) { 1 => 1, 2 => 1, 4 => 1 } Set(3) { 1, 2, 3 }
Map(3) { 1 => 1, 2 => 1, 4 => 0 } Set(3) { 1, 2, 3, 4 }
Map(2) { 1 => 0, 2 => 1 } Set(4) { 1, 2, 3, 4 }
Map(1) { 2 => 0 } Set(4) { 1, 2, 3, 4 }

위의 코드를 보면 Map()함수는 반복문을 돌면서 점차 값의 개수가 사라지는 것을 볼 수 있고 Set()함수는 반대로 계속 넣어주고 있으므로 증가하고 있다. 쉽게 말해 Map()은 전체 배열에서 점차 원소를 지우는 방식, Set()은 중복은 제거하면서 원소를 늘려가는 방식을 사용했다. freq.get(i)-1는 해당 토핑의 개수를 1개 감소시키는 것이다. 

 

4. 이제 get() 메서드를 사용해서 조건문에 만약에 토핑의 개수가 0이라면 delete() 메서드를 사용해서 삭제했다. 이유는 크게 두 가지이다. 첫 번째로는 공간 복잡도를 최적화하기 위해서다. 토핑 개수가 0인데 그걸 삭제 안 하고 냅두면 공간만 차지한다. 그래서 삭제했다.

그리고 조건 검사 간소화하기 위해서다. 개수가 0인 토핑의 항목이 계속 남아 있으면 정확한 비교를 할 수 없다. 그래서 삭제했다. 이 작업을 통해서 코드의 효율성이 상승한다. 

 

5. 이제 마지막으로 Map()과 Set()의 size 메서드를 사용해서 크기가 같은 경우 +1을 해준다. 위의 경우 Map(3) Set(3)인 경우가 2번 존재하므로 2가 된다. 

 

▶ 배운점

1. 항상 문제 제한사항을 잘 보고 문제에 맞는 최적의 자료구조를 활용하자. 

2. 기존의 해결방식을 고수하지말고 탈피하자.