Skip to main content

작성일 : 2024.11.15

롤케이크 자르기 문제

문제 설명​

롤케이크를 두 조각으로 잘라서 나눠 먹으려고 합니다. 공평한 분배의 기준은 각 조각에 있는 토핑의 종류의 수가 동일해야 합니다.

예시​

토핑 배열: [1, 2, 1, 3, 1, 4, 1, 2]의 경우

  • 공평한 분배의 예:
    1. [1, 2, 1, 3], [1, 4, 1, 2] → 양쪽 모두 3종류
    2. [1, 2, 1, 3, 1], [4, 1, 2] → 양쪽 모두 3종류

제한 조건​

  1. topping 배열
    • 길이: 1 ≤ 길이 ≤ 1,000,000
    • 원소 범위: 1 ≤ 원소 ≤ 10,000
    • 각 원소는 토핑의 종류를 나타내는 번호

해결 코드​

function solution(topping) {
  var answer = 0;
  let bigMap = new Map();
  let littleMap = new Map();

  for (let i = 0; i < topping.length; i++) {
    if (bigMap.has(topping[i])) {
      bigMap.set(topping[i], bigMap.get(topping[i]) + 1);
    } else {
      bigMap.set(topping[i], 1);
    }
  }

  for (let i = 0; i < topping.length; i++) {
    if (bigMap.get(topping[i]) === 1) {
      bigMap.delete(topping[i]);
    } else {
      bigMap.set(topping[i], bigMap.get(topping[i]) - 1);
    }
    if (littleMap.has(topping[i])) {
      littleMap.set(topping[i], littleMap.get(topping[i]) + 1);
    } else {
      littleMap.set(topping[i], 1);
    }
    if (bigMap.size === littleMap.size) answer++;
  }
  return answer;
}

알고리즘 설명​

  1. 초기화 단계

    • bigMap: 전체 토핑의 종류와 개수를 저장
    • littleMap: 잘린 왼쪽 부분의 토핑 종류와 개수를 저장

  2. 자르기 시뮬레이션

    • 순차적으로 토핑을 littleMap으로 이동
    • bigMap에서는 해당 토핑 개수 감소
    • 개수가 0이 되면 해당 토핑 삭제

  3. 공평 확인

    • bigMap과 littleMap의 size(토핑 종류의 수)가 같으면 공평한 분배

핵심 문법 요소​

  1. Map 객체의 주요 메서드
// 요소 존재 확인
bigMap.has(topping[i]);

// 요소 개수 확인
bigMap.get(topping[i]);

// 요소 추가/수정
bigMap.set(topping[i], count);

// 요소 삭제
bigMap.delete(topping[i]);

// 맵의 크기(키의 개수) 확인
bigMap.size;

시간 복잡도​

  • O(n): 배열을 두 번 순회
  • n은 topping 배열의 길이

공간 복잡도​

  • O(k): 두 개의 Map 객체 사용
  • k는 서로 다른 토핑의 종류 수

최적화 포인트​

  1. Map 사용

    • 토핑 종류의 빠른 검색과 수정
    • size 속성으로 토핑 종류 수 즉시 확인

  2. 한 번의 순회로 모든 경우 확인

    • 투 포인터와 유사한 접근
    • 점진적으로 토핑을 이동하며 확인