[개발자 면접 준비] 파티션 라벨 - Partition Labels

처음 이 문제를 만났을 때, 저는 현재 문자의 마지막 위치를 찾으려고 매번 문자열을 뒤에서부터 다시 스캔했습니다. 이중 루프가 생기면서 시간 복잡도가 $O(N^2)$이 됐고, 길이가 긴 문자열에서 TLE를 맞았습니다. "마지막 등장 위치를 미리 계산해두면 된다"는 핵심 인사이트를 떠올리기까지 꽤 오래 걸렸습니다.

그 다음에는 파티션 크기를 end - start로 계산해서 답이 계속 1씩 작게 나왔습니다. end - start + 1이 맞는데, 인덱스가 inclusive라는 걸 순간 잊었던 거죠. LeetCode 토론을 보면 이 +1 실수가 놀랍도록 많이 등장합니다. 또 파티션이 끝난 뒤 다음 시작점을 i가 아닌 i + 1로 설정해야 하는데, 이걸 end나 i로 잘못 설정해 파티션이 겹치는 사례도 빈번합니다.

문제 요약

소문자만으로 이루어진 문자열 S가 주어집니다. 문자열을 가능한 많이 파티션으로 나누고 싶어요. 각 파티션 안에서는 같은 문자가 하나의 파티션에 최대한 많이 모이도록 해야 합니다. 파티션 크기 리스트를 반환하세요.

예시

Input	"ababcbacadefegdehijhklij"
Output	[9, 7, 8]
Explanation	파티션은 "ababcbaca", "defegde", "hijhklij" 입니다. 각 파티션 안에 같은 문자가 모두 포함돼 있어요.

커뮤니티에서 반복되는 실수들

이 문제에서 면접 후기와 LeetCode 토론에 반복해서 등장하는 실수를 정리하면 다음과 같습니다.

• 마지막 위치를 미리 계산하지 않고 매번 탐색: 각 문자의 마지막 등장 인덱스를 첫 번째 패스에서 미리 구해두지 않으면, 탐색 중에 매번 남은 문자열을 다시 스캔하게 됩니다. 이렇게 하면 $O(N^2)$이 되어 긴 입력에서 TLE가 납니다.
• 경계 확장 없이 첫 마지막 위치에서 바로 파티션 종료: 예를 들어 "abba"를 처리할 때, a의 마지막 위치가 3인데 인덱스 0에서 바로 파티션을 끊으려는 실수입니다. b도 이 파티션 안에 포함해야 하므로 end를 확장해야 합니다.
• 파티션 크기를 end - start로 계산: 인덱스가 inclusive이므로 end - start + 1이 맞습니다. 이 +1을 빠뜨리면 모든 파티션 크기가 1씩 작게 나옵니다. 저도 처음에 이걸 빠뜨려서 출력이 [8, 6, 7]로 나왔습니다.
• 다음 파티션 시작점을 end로 설정: 현재 파티션이 끝난 뒤 다음 시작점은 i + 1 (또는 end + 1)이어야 합니다. end 자체를 시작점으로 쓰면 한 칸이 두 파티션에 포함됩니다.

풀 실제 흐름 (Thought Process)

• 1단계: 문자열을 한 번 훑어 각 문자의 마지막 등장 인덱스를 기록합니다. 이게 핵심 전처리입니다.
• 2단계: 시작(start)과 끝(end) 포인터를 두고 문자열을 다시 순회합니다.
• 3단계: 현재 문자의 마지막 위치가 end보다 크면 end를 확장합니다. 이 파티션이 더 길어져야 한다는 신호입니다.
• 4단계: 현재 인덱스 i가 end와 같아지면 파티션을 확정합니다. 크기를 end - start + 1로 추가하고, 다음 시작점을 i + 1로 갱신합니다.

Java 구현

public List<Integer> partitionLabels(String S) {
    // 1단계: 각 문자의 마지막 등장 인덱스 미리 계산
    int[] lastIdx = new int[26];
    char[] arr = S.toCharArray();
    for (int i = 0; i < arr.length; i++) {
        lastIdx[arr[i] - 'a'] = i;
    }

    List<Integer> result = new ArrayList<>();
    int start = 0, end = 0;

    for (int i = 0; i < arr.length; i++) {
        // 현재 문자의 마지막 위치로 경계 확장
        end = Math.max(end, lastIdx[arr[i] - 'a']);

        if (i == end) {
            // 파티션 종료: end - start + 1 이 크기 (+ 1 필수!)
            result.add(end - start + 1);
            start = i + 1; // 다음 파티션 시작점은 i + 1
        }
    }
    return result;
}

"abba" 케이스를 머릿속으로 돌려보면 이 코드의 동작이 명확해집니다. a의 마지막 위치는 3, b의 마지막 위치는 2입니다. i=0에서 end=3으로 설정되고, i=1에서 end=max(3,2)=3 유지, i=2에서 동일, i=3에서 i==end가 되어 파티션 크기 3-0+1=4가 확정됩니다. 전체가 하나의 파티션입니다.

복잡도 분석

시간 복잡도: 문자열을 두 번 순회하므로 O(N).
공간 복잡도: 알파벳 26개만 저장하면 되니 O(1) (결과 리스트 제외).

면접 팁

• 마지막 위치 선계산이 왜 필요한지 설명하세요. "각 문자가 마지막으로 등장하는 위치를 미리 알아야 파티션을 어디까지 확장해야 하는지 알 수 있습니다. 이걸 매번 찾으면 $O(N^2)$이 되므로 첫 패스에서 전처리합니다."
• 경계 확장 로직을 말로 설명하세요. "현재 파티션에 들어온 문자가 이 파티션 밖에서도 등장한다면, 파티션을 그 마지막 위치까지 늘려야 합니다."
• 파티션 크기 계산에서 +1을 언급하세요. "인덱스가 inclusive이므로 end - start + 1입니다"라고 명확히 말하면 꼼꼼한 인상을 줍니다.
• 엣지 케이스: 모든 문자가 같은 경우("aaaa"는 [4]), 모든 문자가 다른 경우("abcd"는 [1,1,1,1])를 먼저 언급해두면 좋습니다.

마무리

이 문제의 핵심은 "각 문자의 마지막 등장 위치를 미리 알아야 한다"는 그리디 인사이트입니다. 그 인사이트를 떠올리면 구현 자체는 단순합니다. 면접에서 막히더라도 "문자마다 마지막 위치가 필요한데, 이걸 어떻게 효율적으로 알 수 있을까요?"라고 스스로 질문을 던지면 풀림이 보입니다. 그리고 반드시 end - start + 1과 start = i + 1을 기억하세요. 이 두 줄이 틀리면 답이 맞아도 출력이 달라집니다.