763. Partition Labels - JAVA

문제 LINK

난이도 : 미디움

Top LIKE 100 문제

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

내용

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

-> ... 처음에 영어 실력이 딸려서 무엇으로 나누는 지 이해하지 못하였습니다.
A, B, C 파트 이런식으로 있을 때, 각각의 파트 내에 겹치는 알파벳이 없어야 합니다.
위의 조건으로 가장 많이 쪼갤 수 있는 경우를 List에 파트별 길이를 저장하면 됩니다.

풀이

깔끔한 풀이 및 설명
https://bcp0109.tistory.com/205

접근 : 그리디

각 파트 내에 겹치는 문자가 없어야 한다 ->해당 문자가 언제 나타나는 지 알아야 한다
-> 왼쪽부터 단계별로 이동하며 부분 문자열 내에서 가장 크게 만들 수 있는 위치를 파악해나간다.
-> 이동하고 있는 위치와 크게 만들 수 있는 위치값이 동일한 경우 그때 파티션을 나눈다.

미리 사전에 각 문자가 마지막에 나타나는 위치를 알고 있음.

왼쪽 시작부터 찾아나가면서 가장 큰 인덱스 값을 비교합니다.

이때 만약 loop 위치 i번째와 동일하다면 쪼개고 위치를 저장합니다.

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 문자가 언제 마지막으로 나왔는 지 INDEX 
        int lastIdx [] = new int [26];
        List a = new ArrayList<>();
        for(int i=0;i<s.length();i++){
            lastIdx [s.charAt(i) - 'a'] = i;
        }
        // 가장 큰 INDEX
        int maxIdx = 0;
        // 이전에 쪼개진 INDEX
        int prevIdx = 0;

        for(int i=0;i<s.length();i++){

           maxIdx = Math.max(lastIdx[s.charAt(i)-'a'], maxIdx);

           if(i==maxIdx){
               a.add(i+1-prevIdx);
               prevIdx = i+1;
           }     
        }

        return a;
    }
}

다시 생각해보고 풀어보기.