[Javascript] 롤케이크 자르기

목차

1. 문제 설명
2. 문제 풀이
3. 정답 코드

 

1. 문제 설명

다음 문제는 롤케이크를 자르는 문제이다.

롤케이크에는 토핑이 올라가 있으며, 토핑의 종류는 숫자로 표시된다. (ex. 1, 2, 3...)

철수는 롤케이크를 2조각으로 나눠 동생과 나눠가져야하는데,

공평하게 나누기 위하여 다음 조건을 만족해야한다.

=> 토핑의 가지수가 동일해야 함

 

이 때, topping의 개수가 1,000,000로 매우 큰 숫자임을 주의해야한다.

 

 

2. 문제 풀이

topping의 개수가 1,000,000로 매우 큰 숫자이므로, 롤케이크를 자르는 행위는 선형 탐색으로 해결해야한다는 것을 알았다.

 

변수

각 조각이 가진 토핑들을 저장할 객체와 가짓 수를 카운트할 변수를 선언해야한다.

 

로직

1. 초기 상태 : 모든 토핑을 오른쪽 조각에 우선 배치한다.

2. 왼쪽에서 오른쪽으로 한 조각씩 이동하면서 자른다.

3. 양쪽의 토핑 가짓수가 같다면 카운트를 증가한다.

3. 정답 코드

function solution(topping) {
  var answer = 0;

  // 각 조각이 가진 토핑들을 저장하는 객체
  let left = {}; // 왼쪽 조각: {토핑 번호: 해당 토핑의 개수}
  let right = {}; // 오른쪽 조각: {토핑 번호: 해당 토핑의 개수}

  // 각 조각이 가진 토핑의 종류 수를 카운트
  let leftToppingTypes = 0; // 왼쪽 조각의 토핑 종류 수
  let rightToppingTypes = 0; // 오른쪽 조각의 토핑 종류 수

  // 1. 초기 상태: 모든 토핑을 오른쪽 조각에 배치
  for (const v of topping) {
    if (!right[v]) {
      right[v] = 1;
      rightToppingTypes += 1; // 새로운 종류의 토핑이 추가될 때만 증가
    } else {
      right[v] += 1;
    }
  }
    
  // 2. 왼쪽에서 오른쪽으로 한 조각씩 자르면서 공평한 분배 찾기
  for (let i = 0; i < topping.length - 2; i++) {
    const cur = topping[i]; // 현재 처리할 토핑 번호
    
    // 오른쪽 조각에서 토핑 하나 제거
    right[cur] -= 1;
    if (right[cur] === 0) {
        // 해당 종류의 토핑이 오른쪽에서 아예 사라진 경우
      rightToppingTypes -= 1;
    }
    
    // 왼쪽 조각에 토핑 하나 추가
    if (!left[cur]) {
      left[cur] = 1;
      leftToppingTypes += 1; // 새로운 종류의 토핑 추가
    } else {
      left[cur] += 1;
    }
    

    // 양쪽의 토핑 가짓수가 같다면, 카운트 증가
    if (leftToppingTypes === rightToppingTypes) {
      answer += 1;
    }
  }
  return answer;
}

 

문제 바로가기

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