.leetcode(763. Partition Labels)

문제

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

문제 해설

• 문제는 같은 단어는 무조건 같은 블록으로 보면서 여러 블록으로 나누는 수가 가장 많은 방법을 찾는 것이었다.
  • ex) ABBAC => 2개(ABBA, C)
    • 왜냐하면 A라는 글자는 한 블록안에 있어야하므로 마지막 A가 나올때까지는 무조건 한블럭으로 본다.
  • ex) ABCAC => 1개(ABCAC)
    • 왜냐하면 A라는 글자만 보면 마지막 A가 나오는 ABCA까지를 한블록 후보자로 볼 수 있는데 그 사이에 B,C가 있으므로 마지막 B,C가 나오는데까지를 한 블록으로 봐야한다. 따라서 ABCAC가 한 블록이고 리턴은 1개가 된다.

문제 풀기 전

1. (문제이해를 잘못한 상태) 가장 많은 글자를 포함하되 가장 많이 쪼개라 글자의 갯수>= 2
2. (문제이해를 잘못한 상태) 문제를 쪼개서 서브 문제로 만들 수 있지 않을까.
3. (문제이해를 잘못한 상태) brute force로 해볼까.
4. 문제를 잘못 파악했구나..
5. start,end를 잡아서 어떻게 하면 되겠다는 방법만 알았는데 풀지를 못했다.

직접 푼 풀이

소요시간: 70분(20:53 ~ 10:03)

못풀었다. 재도전하기!

느낀점

1. Greedy방법으로 풀 수 있음을 알게 되었다.
2. 구간들의 확장에 대한 문제를 풀때 greedy를 이용해야겠다. 여러 구간의 확장을 어떻게 시킬지 방법을 몰랐는데 마지막 지점을 저장해두고 나서 기준값을 마지막구간값으로 Math.max로 업데이트하고 현재 인덱스와 그 값이 같을때를 한 구간으로 본다는 식으로 풀면된다.
3. easy풀다가 medium넘어가니 바로 막히는게 참 신기하였다. 내공이 많이 필요하다.

솔루션 공부 후 추가로 푼 풀이

#Greedy
class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> ret = new ArrayList<>();
        int[] alphabets = new int[26];    

        for(int i=0; i<S.length(); i++) {
            int letter = (int)(S.charAt(i)-'a');
            alphabets[letter]=i;
        }

        int far = 0;
        int start = 0;
        for (int i=0; i<S.length(); i++) {
            int letter = (int)(S.charAt(i)-'a');
            far = Math.max(alphabets[letter], far);
            if (far == i) {
                int distance = far - start +1;
                start = far + 1;
                ret.add(distance);
            }
        }
        if (start != S.length()) {
            ret.add(S.length() - start);
        }

        return ret;
    }    
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)