cleanUrl: /posts/partition-labels-leetcode-763

이렇게 해서 풀리겠어? 하고 submit 했는데 풀려서 놀램...;;

Partition Labels - LeetCode

문제

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

• example

접근 방법

s = "ababcbacadefegdehijhklij"

• 각 문자열 별 마지막 위치

1. 첫번째 문자열에 대하여
   • 위와 같이 문자열이 주어졌을때 s[0] 은 반드시 처음에 포함되어서 파티션을 나눠야 한다.
   • 그럼 s[0] 의 마지막 위치는 어디일까? → s[8] 이 마지막이다
   • 따라서, 첫번째 파티션은 길이가 9 이다.
2. 언제 파티션을 나눠야 할까?
   • s[0] 이 마지막에 나타나는 위치
   • 시작 으로 분류 했던 문자열이 마지막으로 나타나는 위치
3. 그 다음 시작 문자열인 "d" 에 대하여
   • "d" 의 시작 위치는 9, 마지막 위치는 14 이다.
   • "d" 다음인 "e" 의 시작 위치는 10, 마지막 위치는 15 이다.

일단 더 생각해보면 끝이 없다 길이는 최대 500 인데 500개를 다 생각해 볼 수 없다.

1, 2, 3 번을 살펴보며 중요하게 체크하는 data 는 어떠한 문자열의 마지막 위치를 구하는 것이다

따라서 다음과 같은 연산을 먼저 수행해둘 필요가 있다.

// 모든 알파벳의 마지막 위치를 기록한다
int[] end = new int[26];
for (int i = 0; i < s.length(); i ++) {
    char c = s.charAt(i);
    int index = c - 97;
    end[index] = i;
}

0 → a, 1 → b, .... 25 → z 로 매핑한다 int index = c - 97; 이런건 algorithm 에서 문자열을 arr 와 매핑시켜 기록하고자 할때 많이 사용하는 idiom 이라 여기고 외워둘 필요가 있다.