[Greedy][Medium] 763. Partition Labels.

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

 

 

Q. 문자열 s 가 입력으로 있을 때, 한 파티션에만 해당 문자가 존재하도록 최대한 많은 파티션을 구성하고, 그 각 길이를 반환해라. 

 

 

Solution. 

  문제 해독에 우선 정확성을 기해야 한다. 

  위 예제에서 보듯이 전체 문장안에서 파티션을 나누되, 파티션 안에는 그 안에만 존재하는 문자들로 이루어져 있어야 한다. 크게 나누면 더 쉬운 확률로 가능해 지지만, 최대한 많이 나눠서 반환하라는 것이 문제이다. 

 

  문제를 이해했으니, 최적해를 찾는 로직을 구상해 본다. 

 

 

  s의 첫번째 char, a가 등장하는 마지막 위치를 찾는다. 

  s의 두번째 char, b 가 등장하는 마지막 위치를 찾는다. 찾아보니, a의 마지막 위치보다는 작다. 

  다음 캐릭터는 a 므로 첫번째와 같다. 

  다음은 b므로 두번째와 같다. 

  다음은 c이고, 이것은 a보다는 작다. 

  주욱 하다보니, a의 마지막 등장위치가 현재와 같아 졌다. 

     -> 이때 우리는 이 파티션 안에 이 안에만 있는 문자들로만 구성되었음을 확신할 수 있다. 

     -> 즉, 등장하던 단어 중 가장 마지막 위치가 현재 위치가 되면, 이 조건이 된다고 할 수 있다.

     -> 따라서 하나의 파티션을 만들고 그 길이를 얻을 수 있다. 

 

  같은 방식으로 계속 해 본다. 

   d 의 마지막 위치를 구한다. 

   e의 마지막 위치를 구한다. d 보다는 하나 더 뒤이며 이것이 일단 최대다. 

   f의 마지막 위치는 현재다.  

   e, g, d, e 까지 오니 최대 위치가 현재와 같아 졌다. 

     -> 새로운 파티션 조건을 만족한다. 

 

  참고 pic. 

  

위 로직대로 코드를 만들어 본다. 

 

 vector<int> partitionLabels(string s) 
{
    map<char, int> mapPos;
    for(int q = 0; q < s.size(); ++q)
        mapPos[s[q]] = q;

    vector<int> vRet;
    int affect = 0;
    int start = -1;
    for(int q = 0; q < s.size(); ++q)
    {
        affect = max(affect, mapPos[s[q]]);
        if(q == affect)
        {
            vRet.push_back( q - start );
            start = q; 
        }
    }    
    return vRet;
}

   

적당한 결과를 얻었다. 

 

 

Note ) 이 풀이는 해석과 관련 풀이 직관에 크게 좌우된다. 

 따라서 기본적으로 문제 해석에 많은 시간을 기울여야 정제된 로직을 얻을 수 있을 것이다. 

 

 

Reference : https://leetcode.com/problems/partition-labels/solutions/1868842/java-c-visually-explaineddddd/