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

안녕하세요! 오늘은 흔히 보이는 문자열 문제 중 하나인 "파티션 라벨(Partition Labels)"을 풀어볼 거예요. 처음엔 복잡해 보여도, 실제로는 그리디 알고리즘과 투 포인터만 잘 쓰면 쉽게 해결됩니다. 저는 처음에 문제를 보고 포기했었지만, 다음 날 다시 도전해서 깨달음을 얻었어요. 그래서 여러분도 같은 실수를 하지 않도록 경험을 공유합니다.

문제 요약

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

예시

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

풀 실제 흐름 (Thought Process)

• 문자마다 마지막 등장 위치를 기록합니다.
• 시작과 끝 포인터를 두고, 현재 포인터가 가리키는 문자의 마지막 위치가 현재 끝보다 크면 끝을 확장합니다.
• 현재 포인터가 끝과 같아지면 파티션을 마무리하고, 새로운 파티션을 시작합니다.

Java 구현

public List<Integer> partitionLabels(String S) {
    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) { // 파티션 종료 지점
            result.add(end - start + 1);
            start = i + 1; // 다음 파티션 시작점
        }
    }
    return result;
}

복잡도 분석

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

경험 팁 (Experience Injection)

• 문제에 처음 접근할 때는 “문자들이 겹치는 구역을 어떻게 나눌까?” 라는 질문을 스스로 던져보세요.
• 각 문자의 마지막 위치를 미리 기록하면, 투 포인터가 어디까지 가야 할지 바로 알 수 있어요.
• 파티션을 마무리할 때는 현재 인덱스가 끝과 같은지 꼭 확인하세요. 놓치면 파티션이 합쳐져 틀린 답이 됩니다.

마무리

이 문제는 “문자를 어떻게 묶을까?” 라는 직관적인 질문을 떠올리는 것이 핵심이에요. 그리디와 투 포인터만으로도 O(N) 시간에 해결할 수 있으니, 면접에서 자신 있게 설명해 보세요!