.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
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.
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.
// 파티션은 "ababcbaca", "defegde", "hijhklij"입니다.
이것은 각 문자가 최대 한 부분에 나타나도록 하는 파티션입니다.
"ababcbacadefegde", "hijhklij"와 같은 파티션은 s를 더 적은 부분으로 분할하기 때문에 올바르지 않습니다.
ABAP
복사
Example 2:
Input: s = "eccbbbbdec"
Output: [10]
ABAP
복사
Constraints:
•
1 <= s.length <= 500
•
s consists of lowercase English letters.
My solution
문제해석
A라는 글자만 보면 마지막 A가 나오는 ABCA까지를 한블록 후보자로 볼 수 있는데 그 사이에 B,C가 있으므로 마지막 B,C가 나오는데까지를 한 블록으로 봐야한다. 따라서 ABCAC가 한 블록이고 리턴은 1개가 된다.
lastIndexOf() 메서드를 사용해야 특정 문자가 마지막에 나타나는 것을 알 수 있다고 생각했다.
그래서 for문을 돌면서 내부에서 if(lastIndex와 s[i]가 같은 경우) map에 s[i]라는 키의 값을 0으로 세팅했다.
그 전에 map에는 if(!map.has(s[i]))로 가지고 있지 않다면 그냥 값을 1로 주었다. 왜냐하면 여러개 가지고 있는 게 상관없고 그냥 마지막에 그 문자가 나타나는 위치가 중요한 것이기 때문이다.
그리고 (이 map이 이터러블이지만 every가 안돌아가서)[...map].every()를 통해서 모든 프로퍼티키가 0이라는 값을 가지고 있다면 이전에 나왔던 문자들이 전부 lastIndexOf 위치를 지났다고 판단했다.
for (let i = 0; i < s.length; i++) {
if (!map.has(s[i])) map.set(s[i], 1);
if (i === s.lastIndexOf(s[i]))
{ map.set(s[i], 0);
if ([...map].every(v => v[1] === 0)) idxArr.push(i + 1);
} // 여기서 검사하는 것이 불필요한 연산을 줄일 수 있다.
}
Java
복사
그렇다면 해당 인덱스가 최대가 되는 문자열 파티션이라고 생각했고 그 인덱스를 idxArr에 i+1로 추가했다. +1을 한 이유는 slice()의 두번째 인수에 끝 인덱스 -1을 넣어주듯이 +1해서 넣어주는 것과 같다. 나중에 뺄셈을 하기 편하게 하기 위해서다.
if ([...map].every(v => v[1] === 0)) idxArr.push(i + 1);
Java
복사
그래서 완성된 idxArr를 for문으로 돌면서 실제로 필요한 것은 그 파티션들의 길이에 대한 배열이기 때문에 아래의 코드를 작성했다.
for (let i = 0; i < idxArr.length - 1; i++)
partitionLabelsArr.push(idxArr[i + 1] - idxArr[i]);
Java
복사
소스코드
/**
* @param {string} s
* @return {number[]}
*/
const partitionLabels = function (s) {
const partitionLabelsArr = [];
const idxArr = [0];
const map = new Map();
for (let i = 0; i < s.length; i++) {
if (!map.has(s[i])) map.set(s[i], 1);
if (i === s.lastIndexOf(s[i])) map.set(s[i], 0);
if ([...map].every(v => v[1] === 0)) idxArr.push(i + 1);
}
for (let i = 0; i < idxArr.length - 1; i++) partitionLabelsArr.push(idxArr[i + 1] - idxArr[i]);
return partitionLabelsArr;
};
test('TC1', () => {
expect(partitionLabels('ababcbacadefegdehijhklij')).toStrictEqual([9, 7, 8]);
});
test('TC2', () => {
expect(partitionLabels('eccbbbbdec')).toStrictEqual([10]);
});
JavaScript
복사
