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

문제가 다소 난해하지만 많은 사람들이 좋아요를 눌렀기 때문에 꾹꾹 참고 마음을 다잡고 도전한 문제였다. 처음 볼 때는 도저히 문제가 원하는 것을 이해하지 못해서 풀기를 포기하고 다른 문제를 풀었다. 다음 날 다시 도전해서 풀어본 결과 전에는 보이지 않았던 것이 눈에 들어와서 풀 수 있었다. 대단히 어려운 문제는 아니어서 가능했던 것 같다.

 

문제 : 소문자 구성된 스트링 S가 주어진다. 우리는 스트링을 가능한 많이 파티션으로 나누고 싶어한다. 파티션으로 나눠서  각 문자가 최대한 한 파티션에서 가장 많이 나올 수 있도록 하고 싶다. 각 파티션의 사이즈를 담은 리스트를 반환하라.

 

이런 식으로 기획서가 날라오면 한바탕 싸움이 일어날 것 같은 이해도 안 되고 말도 안 되는 문제이다. 예제를 보면 그나마 이해가 갈 것 같다.

 

예제 1:

Input: S = "ababcbacadefegdehijhklij"

Output: [9,7,8]

Explanation: 각 파티션은 "ababcbaca", "defegde", "hijhklij"이다. 파티션을 보면 각 문자가 최대한 한 파티션에 가장 많이 모여있게 되어있다. 만약 파티션을 "ababcbacadefegde", "hijhklij" 이렇게 나눈다면 잘못된 것이다. 위 문제에 명시되어있듯이 우리는 가장 많은 파티션으로 나누는 것이 목적이기 때문이다. 

 

Thought Process

그리디 알고리즘과 Two Pointer를 쓰면 풀 수 있을 것 같다. 처음과 끝을 가르키는 투 포인터를 선언하고 끝을 가르 키는 포인터의 위치는 각 문자열의 가장 마지막 위치 중 큰 값을 사용하면 될 것이다. 예를 들자면 'a'의 가장 마지막 위치는 8이다. 그리고 'b'의 마지막 위치는 6이다. 따라서 b는 a가 속한 파티션에 포함시키는 식이다.

 

• 각 문자열의 위치를 기억할 배열을 하나만든다. 영어 소문자만 존재하므로 크기가 26이면 충분하다.
• 각 문자열의 마지막 위치를 배열에 기록한다.
• 시작, 끝 두 포인터를 만든다.
• S 문자열을 처음 부터 읽으면서 현재 문자열이 기존 문자열의 가장 마지막 위치보다 크면 업데이트한다.
• 만약 현재 위치가 문자열 마지막 위치와 같다면 시작과 끝 포인터를 이용해서 파티션 사이즈를 저장한다.
• S 문자열 이터리이션이 끝나면 파티션 길이를 저장한 리스트를 반환한다.

Java code

    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&lt;Integer&gt; result = new ArrayList&lt;&gt;();
    int start = 0, last = 0;
    for(int i = 0; i &lt; arr.length; i++){
        char c = arr[i];
        last = Math.max(lastIdx[c - 'a'], last);
        if(last == i){
            result.add(last - start + 1);
            start = last + 1;
        } 
    }
    return result;
}

 

위 코드의 시간 복잡도는 S문자열 전체를 2번 읽기 때문에 O(2N)이다. 빅오 표기법으로 하면 O(N)이 될 것이다. 공간 복잡도는 반환할 리스트를 제외하면 26길 이이 상수 배열 사이즈를 사용하므로 O(1)이다.