문자가 겹치지 않게 나누는 최대 구간 길이들

자바스크립트 코딩테스트 문제로 greedy-partition 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium greedy-partition 함수명: maxCharacterPartitionLengths 제한 시간: 300ms

문자열을 서로 겹치지 않는 최대 개수의 연속 구간으로 나누되, 같은 문자가 두 개 이상의 구간에 걸쳐 나타나지 않도록 만드는 문제입니다.

문제 설명

소문자 알파벳으로 이루어진 문자열 s가 주어집니다.

문자열을 여러 개의 연속한 구간으로 나누려고 합니다. 이때 다음 조건을 만족해야 합니다.

• 같은 문자는 오직 하나의 구간에만 등장할 수 있습니다.
• 조건을 만족하는 방법들 중에서 구간 개수가 최대가 되도록 나눕니다.

이렇게 나눴을 때 각 구간의 길이를 순서대로 담은 배열을 반환하는 maxCharacterPartitionLengths 함수를 작성하세요.

예를 들어 s = "abacdeed"라면:

• aba
• cdeed

처럼 나눌 수 있고, 결과는 [3, 5]입니다.

첫 구간에 들어간 a, b는 뒤 구간에 다시 나오지 않고, 둘째 구간의 c, d, e도 앞 구간과 겹치지 않습니다.

제한사항

• 0 <= s.length <= 100,000
• s는 소문자 알파벳(a~z)으로만 이루어집니다.
• 반환값은 조건을 만족하는 최대 구간 분할의 각 길이를 담은 배열입니다.
• 빈 문자열이면 빈 배열을 반환합니다.

예시

• 입력: "abacdeed" → 출력: [3, 5]
• 입력: "ababcbacadefegdehijhklij" → 출력: [9, 7, 8]
• 입력: "eccbbbbdec" → 출력: [10]
• 입력: "abc" → 출력: [1, 1, 1]

힌트

• 어떤 위치에서 구간을 잘라도 되는지 알려면, 현재 구간 안에 들어온 문자들이 앞으로 다시 나오는지 알아야 합니다.
• 각 문자의 마지막 등장 위치를 먼저 구해 두면 구간 끝을 판단하기 쉬워집니다.
• 왼쪽부터 한 번 훑으면서 현재 구간이 반드시 포함해야 하는 가장 먼 위치를 갱신해 보세요.

해설

이 문제의 핵심은 지금 자를 수 있는 가장 이른 위치에서 잘라야 구간 개수를 최대화할 수 있다는 점입니다.

1. 왜 마지막 등장 위치가 중요할까?

예를 들어 문자열이 abac라면, 처음 두 글자 ab까지만 보고 자르고 싶어질 수 있습니다.

하지만 a가 뒤에서 한 번 더 나오므로 ab | ac처럼 자르면 문자 a가 두 구간에 걸쳐 등장하게 됩니다. 즉, 현재 구간에 들어온 문자는 그 문자의 마지막 등장 위치까지는 반드시 함께 가져가야 합니다.

그래서 먼저 각 문자의 마지막 등장 인덱스를 기록합니다.

예: abacdeed

• a의 마지막 위치: 2
• b의 마지막 위치: 1
• c의 마지막 위치: 3
• d의 마지막 위치: 7
• e의 마지막 위치: 6

2. 구간 끝을 어떻게 정할까?

왼쪽부터 순회하면서 현재 구간의 끝 end를 관리합니다.

• 구간 시작점 start를 잡습니다.
• 현재 문자 s[i]의 마지막 등장 위치를 확인합니다.
• end = max(end, last[s[i]]) 로 갱신합니다.

이 뜻은, 현재까지 본 문자들 중 하나라도 더 뒤에서 다시 나오면 그 위치까지 구간을 늘려야 한다는 뜻입니다.

그리고 i === end가 되는 순간, 현재 구간 안에 포함된 모든 문자가 그 구간 안에서 완전히 끝났다는 뜻이므로 여기서 잘라도 안전합니다.

3. 왜 greedy가 맞을까?

i === end가 된 시점보다 더 뒤에서 자르면 현재 구간을 불필요하게 키우게 됩니다. 그러면 뒤쪽에서 만들 수 있는 구간 수가 줄어들 수 있습니다.

반대로 이 시점보다 더 앞에서 자르는 것은 불가능합니다. 왜냐하면 현재 구간 안의 어떤 문자가 뒤에서 다시 나오기 때문입니다.

즉,

• 더 앞은 불가능
• 더 뒤는 손해 가능성 있음

이라서 가능한 가장 이른 지점에서 자르는 greedy 선택이 최적입니다.

4. 풀이 흐름

1. 각 문자의 마지막 등장 위치를 기록합니다.
2. 문자열을 왼쪽부터 순회합니다.
3. 현재 문자들의 마지막 위치 중 최댓값으로 구간 끝을 갱신합니다.
4. 현재 인덱스가 구간 끝과 같아지면 구간 길이를 정답에 추가하고 다음 구간으로 넘어갑니다.

5. 구현 예시

function maxCharacterPartitionLengths(s) {
  const last = new Map();

  for (let i = 0; i < s.length; i++) {
    last.set(s[i], i);
  }

  const result = [];
  let start = 0;
  let end = 0;

  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i]));

    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }

  return result;
}

6. 예시 추적

s = "abacdeed"

• i = 0, 문자 a, end = 2
• i = 1, 문자 b, end = 2
• i = 2, 문자 a, end = 2 → 여기서 자름, 길이 3
• 다음 구간 시작
• i = 3, 문자 c, end = 3
• i = 4, 문자 d, end = 7
• i = 5, 문자 e, end = 7
• i = 6, 문자 e, end = 7
• i = 7, 문자 d, end = 7 → 여기서 자름, 길이 5

결과는 [3, 5]입니다.

7. 복잡도

• 마지막 위치 기록: O(n)
• 한 번 순회: O(n)
• 전체 시간 복잡도: O(n)
• 추가 공간 복잡도: O(1) 또는 O(문자 종류 수)

알파벳 종류가 작을 때 특히 효율적으로 동작하고, 문자열 분할 + greedy 판단 기준을 익히기 좋은 문제입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

입력값 []

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.