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

---

 

● [롤케이크 자르기] Lv2

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

 

 

● 풀이 과정

1. 전체 토핑 종류 및 갯수 파악하기

1-1. map을 이용한다. (토핑: key, 토핑의 갯수: value)

 

2. 왼쪽 토핑부터 하나씩 순회

2-1. set에는 해당 토핑 추가 (중복은 알아서 처리되므로 set 자료구조 이용)

2-2. map에서 해당 토핑 갯수 감소 (감소된 토핑이 0개가 되면 delete)

 

3. set.size 와 map.size 비교

3-1. 동일하면 카운팅 (answer++)

 

 

● 주의 할 것

: 처음에는 set 2개를 이용하여 풀이하려고 하였으나 시간초과를 받았다.

set 1개와 Array 1개를 이용하여 구현하였으나 또 시간초과를 받았다.

 

최대한 순회하는 로직을 제거하였으나 아래와 같은 부분이 문제였다.

1. set의 add메서드는 해당 set에 값이 있는지 순회하는 로직이 암묵적으로 있다.

2. set의 has메서드는 해당 set에 값이 있는지 순회하는 로직이 암묵적으로 있다.

3. 하나씩 토핑을 제거하는 자료구조 쪽에서, 해당 토핑이 몇 개 있는지 확인하기 위해 topping 배열을 순회하게 된다.

3-1. includes와 같은 메서드에는 순회하는 로직이 있다.

 

위와 같이 정제된 데이터를 처리하기 위해 순회하게 되면 시간초과를 벗어날 수가 없었다.

따라서 순회하는 로직을 벗어나기 위해서는 다른 자료구조를 사용했어야했다.

 

매개변수로 주어진 topping을 순회하는 횟수는 2번이 최소라고 생각했다.

1. 정제된 데이터를 만들기 위해 순회

2. 롤케이크 자르기 위한 위치 선정을 위해 순회

 

그리고 정제된 데이터의 자료구조는 set이나 array가 아닌 map으로 선택한 이유는 다음과 같았다.

1. 토핑의 종류 갯수 파악 가능

2. 각 토핑의 갯수 파악 가능

2-1. set을 이용하면 이 정보를 얻을 수 없기에 각 토핑마다 매개변수로 주어진 topping을 순회하여 알아내야 한다.

 

 

● 풀이 코드

function solution(topping) {
  let answer = 0;
  const right = new Map(); // 전체에서 감소 토핑을 하나씩 뺄 예정
  const left = new Set(); // 하나씩 토핑을 추가할 예정

  // 각 토핑이 몇 개씩 있는지 확인
  for (let index = 0; index < topping.length; index++) {
    const key = topping[index];
    if (right.has(key)) {
      const value = right.get(key);
      right.set(key, value + 1);
    } else {
      right.set(key, 1);
    }
  }

  // 왼쪽부터 하나씩 추가,삭제하며 좌우 토핑수 비교하기
  for (let index = 0; index < topping.length; index++) {
    const targetTopping = topping[index];

    left.add(targetTopping);

    const value = right.get(targetTopping);
    if (value === 1) {
      right.delete(targetTopping);
    } else {
      right.set(targetTopping, value - 1);
    }

    if (left.size === right.size) {
      answer += 1;
    }
  }

  return answer;
}

 

 

---