Leetcode - 763. Partition Labels

문제 Leetcode: 763. Partition Labels

https://leetcode.com/problems/partition-labels/

문제 이해

하나의 문자열을 쪼갰을때 각각의 파티션은 중복된 문자가 없어야함. 가장 많이 쪼갤 수 있는 경우의 수 . 출력은 쪼개진 각각의 파티션 문자 갯수 리턴.

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".

문제 해결

Greedy 방법으로 해결.
그리디는 현재 선택이 최선임이 보장 되어야함.
가령 990원을 동전으로 거슬러줄때 가장 적은 수의 동적으로 줘야하는 문제가 있다면, 첫번째 동전의 선택은 500원이 최선의 선택임이 무조건 보장됨.

이 문제에서도 문자열 처음부터 시작하여 현재 포지션의 최적의 상태를 구하고, 나머지 포지션에서도 동일한 방법을 취함. 첫번째 파티션 결정을 미리 해도 이후 결과에 영향을 미치지 않으므로, 가장 최선의 파티션을 선택하면서 문자열 시작부터 끝으로 진행.

O(N)

실행속도 0ms / 100%
26개의 영소문자 key를 갖는 해시테이블 value에 가장 뒤에있는 idx 를 넣는것이 핵심 아이디어

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int* partitionLabels(char * s, int* returnSize){
    int ssize = strlen(s); 
    int end[26] = {0,};
    int *result = (int *)malloc(sizeof(int) * 26);
    int begin_idx = 0; /* base idx for calculating partition */
    int last_idx = 0; /* most last idx at current position */
    *returnSize = 0;
    
    for (int i = 0; i < ssize; i++)
        end[s[i] - 'a'] = i;    /* the hashtable has last_idxes of each charactors */

    for (int i = 0; i <= ssize; i++) {
        if (i > last_idx) { /* time to save the result */
            result[(*returnSize)++] = i - begin_idx;    /* calculate current partition */                       
            begin_idx = i;  /* update for the next result */
        }
        if (i < ssize)      /* prevent out of index by increasing i */
            last_idx = MAX(last_idx, end[s[i] - 'a']);  /* update most last idx from the current loop */
    }
    return result;
}

221207 추가 풀어봄.
해시테이블에 마지막 인덱스 저장까지는 풀었으나, 마지막 값 처리를 제대로 하지 못해서 힌트확인.

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> ret;
        unordered_map<char, int> map;
        for (int i = 0; i < s.length(); i++)
            map[s[i]] = i;

        int last_idx = map[s[0]];
        int begin_idx = 0;
        for (int i = 0; i <= s.length(); i++) {
            if (i > last_idx) {
                ret.push_back(last_idx - begin_idx + 1);
                begin_idx = i;
                last_idx = map[s[i]];
            }
            if (i < s.length()) {
                last_idx = max(last_idx, map[s[i]]);
            }
        }
        return ret;
    }
}

O (N^2)

이것은 처음 시도해서 풀었던 방식 accept는 되었지만 O(N^2) 이고, 좋은 풀이방법이 아니었음.

int partition(char *s, int idx)
{
    int ssize = strlen(s);
    int table_left[26] = {0,};
    int table_right[26] = {0,};
    int pivot = idx + 1;
    bool inc_pivot = false;

    for (; pivot < ssize; pivot++) {
        for (int i = 0; i < 26; i++)
            table_left[i] = table_right[i] = 0;
        for (int i = idx; i < pivot; i++)
            table_left[s[i] - 'a']++;
        for (int i = pivot; i < ssize; i++)
            table_right[s[i] - 'a']++;
        
        for (int i = 0; i < 26; i++) {
            if (table_left[i] && table_right[i]) {
                inc_pivot = true;
                break;
            }
        }
        if (inc_pivot == false)
            return pivot;
        else {
            inc_pivot = false;
            continue;
        }
    }
    return ssize;
}

int* partitionLabels(char * s, int* returnSize){
    int ssize = strlen(s); 
    int pivot = 0, prev = 0;
    int cnt = 0;
    int *arr = (int *)malloc(sizeof(int) * ssize);
    while (pivot < ssize) {
        prev = pivot;
        pivot = partition(s, pivot);
        arr[cnt++] = pivot - prev;
    }
    *returnSize = cnt;
    return arr;
}