[해시] 프로그래머스 '롤케이크 자르기' - js

1. 문제

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

프로그래머스

2. 코드

처음 푼 코드)

Set을 사용하여 모든 경우를 비교하는 간단한 풀이라 당연히 시간초과가 날 것을 예상했다.. 그래도 항상 완탐을 제일 먼저 시도해보아야하니 시간초과를 예상했어도 한 번 작성해보았다.

function solution(topping) {
    let answer = 0;
    
    const check = (arr1,arr2) => {
        let set1 = new Set();
        let set2 = new Set();
        
        for(let i=0;i<arr1.length;i++) set1.add(arr1[i]);
        for(let i=0;i<arr2.length;i++) set2.add(arr2[i]);
        
        return set1.size === set2.size ? true : false;
    }
    
    for(let i=1;i<topping.length;i++){
        let first = topping.slice(0,i);
        let second = topping.slice(i);
        
        check(first,second) ? answer++ : null;
    }
    
    return answer;
}

정답 코드)

이런 유형의 문제는 한 쪽에 전부 넣어주고 하나하나 빼고 더해가면서 경우의 수를 비교하다가 길이가 역전이 되는 순간 break를 하는 방식을 사용해야 시간초과가 나지 않게 된다고 한다.

한 쪽에 전부 넣어주는 것에는 Hash를, 토핑 하나하나 더해가며 비교하는 것에는 Set을 사용하니 시간 초과가 나지 않는다. 확실히 처음보다는 비교 횟수를 줄여주는 것 같다.

function solution(topping) {
  let answer = 0;

  const total = new Map(); // 토핑 종류 및 개수
  const brother = new Set(); // 형의 토핑 종류

  // Map 자료구조에 각 토핑의 개수가 몇개인지 넣어준다.
  // {1 => 4, 2 => 2, 3 => 1, 4 => 1}
  topping.forEach((n) => {
    total.set(n, (total.get(n) || 0) + 1);
  });

  for (let n of topping) {
    // 토핑을 하나씩 확인하면서 total에서 해당 토핑의 갯수를 하나씩 빼준다.
    total.set(n, total.get(n) - 1);

    // 해당 토핑을 brother Set에 넣는다.
    brother.add(n);

    // total에서 현재 토핑의 갯수가 0이되면 그 토핑을 지워준다.
    if (!total.get(n)) total.delete(n);

    // total의 크기와 brother의 크기가 같으면 answer을 1 증가시켜준다.
    if (total.size === brother.size) answer++;

    // 형이 가진 토핑 종류가 많아지면 이 이후로는 형의 토핑 개수만 증가하는 것이기 때문에
    // break를 통해 비교를 종료한다.
    if (total.size < brother.size) break;
  }

  return answer;
}

 

복기

6/15