763. Partition Labels

• 풀지 못했다. 가장 많은빈도수에 오른 문제임에도 불구하고. 처음 풀어보는 문제였는데. 못풀었다. 
• 그동안 풀었던 문제는 사실 한번씩 풀어봤던 문제들이다. 그래서 쉬웠고, 그래서 한번에 통과도 하고 그랬던 것이다.
• 처음보는 문제는 또 이렇게 당황하고, 접근을 못한다.
• 각 알파벳의 처음과 마지막 index 를 찾아서, (a,b) 이런식으로 만들고,  겹치는 알파벳들은 merge  하면 될것 같았다.
• 하지만 그렇게 하면 merge  를 하더라도 문제에서 말하는 답을 return 하기엔 또 정렬을 하고, 계산을 해야한다.

• 생각해보니, 어떤 인도인에게 이 질문을 받은것 같기도 하다.그때.
• I said "infinite" 이라면서. infinite pool 에 알파벳들이 있는데. 하나씩 꺼낼수 있고, 이럴때 한번만 나타나도록 partition 을 구하라고 했었다. 
• 그때도 못풀었고, 지금 역시,  infinite  가 아닌데도, 못풀었다. 비슷한 문제인지 조차도 한참 뒤에 알았다.
• 그때 당시엔 새로운 문제인줄 알았는데. 새로운 문제가 아니었다. 수많은 문제 은행 속 문제중에 내가 아직 안풀었던 것 뿐. 이미 2018년도에 누군가들이 풀었던 문제들이었던 거다. 나는 몰랐다가, 2019년 6월에 처음 그 문제를 인도인한테 접했고.

끝내 풀지 못한 내 풀이는 장황하고,  두서없고, 결론을 맺지 못했다. 그러나 역시 정답은 생각보다 간결하고 깔끔했다. 늘 그렇다.

각각의 알파벳 캐릭터의 가장 마지막 index 를 배열 26개에 관리한다. 

그리고 for 를 toCharArray() 에 대해 돌면서 각 index 별로 그 캐릭터의 last index 를 가져와 last  라는 변수에 저장한다. 

그리고 이렇게 유지한  last 와 현재 캐릭터의 last index 중 max 값을 last 에 계속 유지한다. 

그래서, 현재 index  가 last  와 동일하면, 그 사이에 나타난 캐릭터들의 last index  가 last 라 보다 작다는 뜻이고, 여기서 partition 을 할 수 있다는 것이다. 

그리고 그 다음 index  부터 또 반복한다.

public List<Integer> partitionLabels(String S) {
    int[] last = new int[26];
    for (int i = 0; i < S.length(); ++i)
        last[S.charAt(i) - 'a'] = i;

    int j = 0, anchor = 0;
    List<Integer> ans = new ArrayList();
    for (int i = 0; i < S.length(); ++i) {
        j = Math.max(j, last[S.charAt(i) - 'a']);
        if (i == j) {
            ans.add(i - anchor + 1);
            anchor = i + 1;
        }
    }
    return ans;
}