[Leet code - 763] Partition Labels ✅

Partition Labels - LeetCode

 

문제

Input : 문자열 s

Output : s를 규칙에 따라 가장 많은 구간으로 나누고 각 구간의 개수 반환

Rule : 한 종류의 알파벳은 하나의 구간에만 속할 수 있다.

 

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

 

문자열 s의 길이가 최대 500이므로 $O(n^2)$부터 고려해 볼 수 있다.

 

 

해결 과정

처음에는 자연스럽게 완전 탐색같은 방법을 생각했다.

첫 알파벳의 구간을 확인하고, 그 안에 있는 알파벳의 구간을 확인하고 또 그 안에 있는 알파벳의 구간을 확인하고, ...

더 확인한 알파벳이 없을 때까지 반복하여 하나의 구간을 찾는 방법이었다.

 

해당 방법은 $O(n \log n)$의 복잡도를 가지므로 더 빠른 복잡도를 가진 방법이 없는지 생각해 보다가

괜찮은 아이디어를 생각했는데, 그룹의 마지막 index를 업데이트해나가는 방법이었다.

 

1. 우선 첫 번째로 만나는 알파벳을 기준으로 그룹의 마지막 index인 end가 정해진다.

 

2. 순회를 하면서 만나는 알파벳의 마지막 index와 비교해 더 큰 값을 그룹의 마지막 index로 갱신한다.

 

3. 순회하면서 순회 중인 index가 마지막 index와 같다면 하나의 그룹을 끝맺는다.

 

여기까지가 핵심 아이디어로 순회를 한 번만 하기 때문에 $O(n)$의 복잡도를 가져 더 빠르다고 볼 수 있다.

 

 

구현

vector<int> partitionLabels(string input) 
{
    // 각 알파벳의 마지막 위치를 저장
    int alpEnd['z' + 1] = {0};

    int i = 0;
    for (char c : input)
    {
        alpEnd[c] = i++;
    }


    //현재 탐색중인 그룹의 시작과 마지막 인덱스 저장
    // -1을 가지고 있다면 그룹의 초기화를 해야한다는 의미로 사용했다.
    int start = -1;
    int end = -1;


    vector<int> result;
    for (int s = 0; s < input.size(); ++s)
    {
        int nowChar = input[s];
        int nowIdx = alpEnd[nowChar];

        //  그룹의 시작이면 start와 end를 초기화한다.
        if (start == -1)
        {
            start = s;
            end = nowIdx;
        } 

        // 그룹의 끝인지 확인
        if (s == end)
        {
            result.push_back(end - start + 1);
            start = -1;
            continue;
        }

        // 그룹의 중간 idx면 end를 업데이트한다.
        if (s < end)
        {
            end = std::max(end, nowIdx);
        }
    }

    return result;
}

 

 

되돌아보기

생각했던 아이디어가 가장 괜찮은 아이디어였지만 구현하기 뭔가 까다로웠다..

약간 로직에서 부분코드 1, 부분코드 2, 부분코드 3 이렇게 있다면,

1번이 먼저여야 할까? 3번이 먼저인가? 이런 순서도 생각했고

if문의 다른 예외도 있는데 이건 부분코드 4로 만들어야 하나? 이런 추가적인 상황도 같이 두서없이 고려하느라 뭔가 구현이 잘 안 된 것 같았다.

 

그래서 작성했던 의사 코드를 지우고 우선 상황을 확실히 했었는데 이게 좀 괜찮은 방법 같다.

i < end  인경우, i == end 인 경우, i > end인 경우 이렇게 나누고 각 상황에서는 어떤 로직이 들어가야 하는지 생각했더니 좀 수월하게 구현이 가능했다.

 

막상 상황을 나누고 나니까 상황이 그렇게 많지 않네?라는 생각도 들어 진작 이렇게 할 걸 그랬나 생각이 든다.

 

 

개선 코드

다른 사람의 코드에서 좀 더 클린 하게 코드를 작성할 수 있음을 확인했다!

vector<int> partitionLabels(string input) {
    
    // 각 알파벳의 마지막 위치를 저장
    int alpEnd['z' + 1] = {0};

    for (int i = 0; i <s.size(); ++i)
    {
        alpEnd[input[i]] = i;
    }


    vector<int> result;
    int start = 0, end = 0;

    for (int s = 0; s < input.size(); ++s)
    {
        // end는 항상 업데이트해도 문제가 없다.
        end = std::max(end, nowIdx);

        // 그룹이 끝날때만 확인하면 됐었다.
        if(i == end) 
        {
            result.push_back(end - start + 1);
            start = i + 1;
        }
    }

    return result;
}