JavaScript로 중복 문자를 한 번만 남기고 사전순 최소 문자열 만들기

문제 소개

하나의 문자열 str을 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 입력 문자열을 기반으로 새로운 문자열을 만들어야 하며, 새 문자열에는 각 문자가 정확히 한 번씩만 나타나야 합니다. 또한 어떤 위치의 문자를 남길지 선택할 때는, 그 선택이 결과 문자열을 사전순(lexicographically)으로 가장 작게 만들도록 해야 합니다.

예를 들어 함수의 입력이 다음과 같다면 −

const str = 'cbacdcbc';

출력은 다음과 같아야 합니다 −

const output = 'acdb';

출력 설명

문자열에는 'c'가 여러 번 등장하지만, 그중 어떤 'c'를 남기더라도 결과에는 한 개의 'c'만 포함됩니다. 이때 첫 번째 'c'를 제거하는 것이 결과 문자열을 사전순으로 가장 작게 만듭니다. 'a'와 'b'의 경우도 같은 원리가 적용됩니다.

구현 코드

이 문제는 그리디(Greedy) 알고리즘과 스택을 활용하면 깔끔하게 해결할 수 있습니다.

const str = 'cbacdcbc';

const removeDuplicates = (str = '') => {
  // 길이가 1 이하인 문자열은 그대로 반환
  if (str.length <= 1) {
    return str;
  }

  // 각 알파벳이 마지막으로 등장하는 인덱스를 기록
  const lastIndex = new Array(26).fill(-1);
  for (let i = 0; i < str.length; i++) {
    lastIndex[str.charCodeAt(i) - 97] = i;
  }

  const stack = [];                    // 결과 문자를 쌓을 스택
  const used = new Array(26).fill(false); // 스택에 포함된 문자 표시

  for (let i = 0; i < str.length; i++) {
    const ch = str[i];
    const code = str.charCodeAt(i) - 97;

    // 이미 결과에 포함된 문자라면 건너뜀
    if (used[code]) continue;

    // 스택 맨 위 문자가 현재 문자보다 크고,
    // 뒤에 다시 등장한다면 제거해서 사전순을 개선
    while (
      stack.length > 0 &&
      stack[stack.length - 1] > ch &&
      lastIndex[stack[stack.length - 1].charCodeAt() - 97] > i
    ) {
      const removed = stack.pop();
      used[removed.charCodeAt() - 97] = false;
    }

    stack.push(ch);
    used[code] = true;
  }

  return stack.join('');
};

console.log(removeDuplicates(str));

코드 설명

핵심 아이디어는 다음과 같습니다 −

첫째, 문자열을 한 번 순회하면서 각 알파벳이 마지막으로 등장하는 위치를 미리 기록해 둡니다. 이 정보는 "지금 버려도 나중에 다시 선택할 수 있는 문자인가?"를 판단하는 데 사용됩니다.

둘째, 문자열을 왼쪽에서 오른쪽으로 순회하면서 결과를 스택에 쌓습니다. 이때 스택 맨 위의 문자가 현재 문자보다 사전순으로 크고, 그 문자가 뒤에서 다시 등장한다면 스택에서 제거합니다. 지금 제거하고 더 작은 문자를 앞쪽에 배치하는 것이 전체 결과를 사전순으로 더 작게 만들기 때문입니다.

셋째, 이미 결과에 포함된 문자는 다시 추가하지 않으므로, 모든 문자가 정확히 한 번씩만 결과에 남게 됩니다.

이 과정을 거치면 각 문자가 한 번씩만 등장하면서도 사전순으로 가장 작은 문자열이 자연스럽게 완성됩니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

acdb