이렇게 해서 풀리겠어? 하고 submit 했는데 풀려서 놀램...;;
문제
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"
Java
복사
각 문자열 별 마지막 위치
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;
}
Java
복사
0 → a, 1 → b, .... 25 → z 로 매핑한다 int index = c - 97; 이런건 algorithm 에서 문자열을 arr 와 매핑시켜 기록하고자 할때 많이 사용하는 idiom 이라 여기고 외워둘 필요가 있다.
(소문자 알파벳 한정, 대문자인 경우 int index = c - 65; )
위와 같은 연산을 해두면 배열 end 에는 각 문자열의 마지막 위치가 저장될 것이다.
그럼 다시 s = "ababcbacadefegdehijhklij" 의 문자열을 순회 하면서 i 번째 문자열의 마지막 위치를 확인하고, 어디서 끊어야 할지 고민해보자
어디서 끊어야(파티션을 생성해야)하는지가 중요하다. 그래야 size 를 체크하지 않겠는가
시작 위치는 중요하지 않다. 0번째, 0이 마지막으로 발생된 위치 그 다음이 시작점 이고, 이 문자열로 파티션을 만들면 그 문자열의 마지막 발생 위치 다음이 파티션 생성지점이다.
즉, 기록하며 확인해야 하는건 i 번째 문자열이 어디서 마지막 발생하며 그 위치가 가장 긴 것을 찾아내보자
int longest = 0;
List<Integer> result = new ArrayList<>();
int size = 0;
for (int i = 0; i < s.length(); ++ i) { // 다시 문자열 s를 순회한다.
int last = end[i]; // 지금 문자열 마지막 위치
// 기존에 저장된 마지막 위치와 현재 문자열의 마지막 위치를 비교하여 더 멀리 있는 위치를 찾는다
longest = Math.max(end[last], longest);
// 파티션을 생성하는 위치 -> 현재 i가 longest 이다
if (longest == i) {
result.add(size+1);
size = 0; // 파티션을 생성했으니 사이즈를 초기화 하자
} else (longest > i) {
// 예를 들어, s[i] -> e 인데 현재 11이고 마지막 위치가 15 이다.
// 아직 자를 때가 아니다
size ++;
}
// longest < i -> 이런 상황이 올 수 있을까?
// "잘라야 하는 위치가 뒤에 있다" 이런 상황은 버그이므로 고쳐야 한다.
}
Java
복사
작성한 알고리즘은 다음과 같다
class Solution {
public List<Integer> partitionLabels(String s) { // -97
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;
}
int max = 0; // 실제 풀 때는 걍 max 라는 이름을 사용함
List<Integer> result = new ArrayList<>();
int size = 0;
for (int i = 0; i< s.length(); ++ i) {
int lastIndex = s.charAt(i) - 97;
max = Math.max(end[lastIndex], max);
if (max == i) {
result.add(size+1);
size = 0;
} else if (max > i) {
size += 1;
}
}
}
}
Java
복사
사실 submit 해본 이유가 뭔가 놓친게 있을거 같아서 틀린 값을 보고 힌트를 얻으려고 submit 을 실행한건데...
결과 보니 더 효율적인 알고리즘이 있을거 같지만.... 새벽 5시 24분 이니깐 일단 자야겠다 ㅠ
