[프로그래머스] 메뉴 리뉴얼

메뉴 조합 문제 해결기 - 문자열 정렬의 중요성

오늘 코딩테스트에서 메뉴 조합 문제를 만났는데, 처음엔 간단해 보였지만 실제로는 문자열 정렬이라는 중요한 포인트를 놓쳐서 한참을 헤맸다. 문제 해결 과정을 정리해보자.

문제 이해

orders 배열과 course 배열이 주어진다. orders의 각 문자열에서 가능한 모든 조합을 만들고, course에 지정된 길이별로 가장 많이 주문된 조합을 찾는 문제다.

예시:

• orders: ["XYZ", "XWY", "WXA"]
• course: [2, 3, 4]
• 기댓값: ["WX", "XY"]

첫 번째 시도 - 기본 조합 생성

처음엔 단순하게 각 문자열에서 조합을 생성하는 방식으로 접근했다.

function solution(orders, course) {
  function findCnt(arr) {
    const countMap = {};

    const generateCombinations = (str, start = 0, current = "") => {
      if (current.length > 0) {
        countMap[current] = (countMap[current] || 0) + 1;
      }

      for (let i = start; i < str.length; i++) {
        generateCombinations(str, i + 1, current + str[i]);
      }
    };

    arr.forEach((str) => {
      generateCombinations(str);
    });

    return countMap;
  }

  // ... 나머지 로직
}

문제 발견

테스트 케이스를 돌려보니 결과가 다르다.

입력: ["XYZ", "XWY", "WXA"], [2, 3, 4]
기댓값: ["WX", "XY"]
실행 결과: ["XY"]

왜 "WX"가 빠졌을까? 디버깅을 위해 findObj를 출력해보자.

findObj: {
  X: 3,
  XY: 2,
  XYZ: 1,
  XZ: 1,
  Y: 2,
  YZ: 1,
  Z: 1,
  XW: 1,  // 여기가 문제!
  XWY: 1,
  W: 2,
  WY: 1,
  WX: 1,  // 이것도 문제!
  WXA: 1,
  WA: 1,
  XA: 1,
  A: 1
}

아하! "WX"가 1번만 카운트되고 있다. 하지만 "XWY"와 "WXA"에서 모두 "WX" 조합을 만들 수 있어야 하는데?

핵심 깨달음

문제는 문자열의 순서였다.

• "XWY"에서 조합을 만들 때 "XW"는 생성되지만 "WX"는 생성되지 않는다
• "WXA"에서도 "WX"는 생성되지만 "XW"는 생성되지 않는다

하지만 실제로는 "XWY"에서도 W와 X를 선택해서 "WX" 조합을 만들 수 있어야 한다. 알파벳의 순서나 위치에 관계없이, 해당 문자들이 포함되어 있기만 하면 조합을 만들 수 있다는 가정이 필요했다.

해결 방법

각 문자열을 조합 생성하기 전에 알파벳 순으로 정렬하자.

// 각 문자열에 대해 조합 생성 (문자열을 정렬해서 처리)
arr.forEach((str) => {
  const sortedStr = str.split("").sort().join("");
  generateCombinations(sortedStr);
});

결과 확인

수정 후 다시 테스트해보자.

findObj: {
  X: 3,
  XY: 2,
  XYZ: 1,
  XZ: 1,
  Y: 2,
  YZ: 1,
  Z: 1,
  W: 2,
  WX: 2,  // 이제 2번으로 올바르게 카운트!
  WXY: 1,
  WY: 1,
  A: 1,
  AW: 1,
  AWX: 1,
  AX: 1
}

완벽하다! 이제 "WX"가 2번 카운트되어서 길이 2인 조합 중 최고 빈도가 되었다.

최종 코드

function solution(orders, course) {
  function findCnt(arr) {
    const countMap = {};

    const generateCombinations = (str, start = 0, current = "") => {
      if (current.length > 0) {
        countMap[current] = (countMap[current] || 0) + 1;
      }

      for (let i = start; i < str.length; i++) {
        generateCombinations(str, i + 1, current + str[i]);
      }
    };

    // 각 문자열에 대해 조합 생성 (문자열을 정렬해서 처리)
    arr.forEach((str) => {
      const sortedStr = str.split("").sort().join("");
      generateCombinations(sortedStr);
    });

    return countMap;
  }

  const findObj = findCnt(orders);
  const result = [];

  // course의 각 정수에 대해 처리
  course.forEach((targetLength) => {
    const filteredKeys = Object.keys(findObj).filter(
      (key) => key.length === targetLength
    );

    if (filteredKeys.length === 0) return;

    const maxValue = Math.max(...filteredKeys.map((key) => findObj[key]));

    // 최고 value를 가진 키들만 선택 (최소 2번 이상 나타난 것만)
    const topKeys = filteredKeys.filter(
      (key) => findObj[key] === maxValue && findObj[key] >= 2
    );

    result.push(...topKeys);
  });

  // 알파벳 순으로 정렬
  result.sort((a, b) => a.localeCompare(b));

  return result;
}

시간복잡도

• 조합 생성: O(2^n) 각 문자열마다
• 정렬: O(n log n)
• 전체적으로 O(m * 2^n) (m은 orders 길이)