LeetCode - Partition Labels (Javascript)

문제 설명

파티션 안에 문자(char)별 최대값이 담기도록 하되, 파티션의 개수는 최대한 많이 분리될 수 있도록 하는 문제였다.

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.

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

---

소스 코드 (1차)

역시나 통과하긴 했지만 처참한 시간 복잡도다..
100ms 이하로 줄여봐야겠다.

const partitionLabels = (s) => {
  const answer = [];
  const charObj = {};
  [...s].forEach((char, i) =>
    charObj[char] ? charObj[char].push(i) : (charObj[char] = [i])
  );
  let tempMax = -Infinity;
  let count = 0;
  let current, end;
  for (let i = 0; i < s.length; i++) {
    current = charObj[s[i]];
    end = current.length - 1;
    if (current[end] > tempMax) tempMax = current[end];
    if (i === tempMax) {
      answer.push(count + 1);
      count = 0;
      tempMax = 0;
      continue;
    }
    count++;
  }
  return answer;
};

---

소스 코드 (최종)

100ms 이하로 런타임을 줄일 수 있었다!
기존 charObj에서의 배열 방식을 버리고, end값만을 담아 사용했더니 시간이 조금 더 줄었다.

const partitionLabels = (s) => {
  const answer = [];
  const charObj = {};
  [...s].forEach((char, i) => (charObj[char] = i));
  let tempMax = -1;
  let count = 0;
  let current;
  for (let i = 0; i < s.length; i++) {
    current = charObj[s[i]];
    if (current > tempMax) tempMax = current;
    if (i === tempMax) {
      answer.push(count + 1);
      count = 0;
      tempMax = 0;
      continue;
    }
    count++;
  }
  return answer;
};

---

풀이 설명

객체에 각 문자별 lastIndex를 담아주는 것이 핵심이다.

[...s].forEach((char, i) => (charObj[char] = i));

// 위의 코드로 인해 charObj는 아래와 같은 형태를 띄게 된다.

// charObj = {a: 6, b: 2, c: 4, d: 5 ....}

위의 그림과 같이, a의 마지막 인덱스까지가 하나의 파티션이 될 수 있고, 두 번째 파티션의 기준은 e의 마지막 인덱스까지가 된다.

따라서, 반복문을 돌며 a,b,c,d… 들의 가장 큰 index값을 구하고, 반복문의 i가 가장 큰 index에 닿으면 이를 하나의 파티션으로 구분해주면 된다.

---