[Leetcode] 763. Partition Labels

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

---

배열(arr)을 하나 만들어서 문자열 S에서 알파벳이 나오는 시작인덱스와 끝인덱스를 저장한다.
S문자열을 탐색하면서 배열을 다 채운뒤 오름차순 정렬한다.
정렬한 배열을 앞에서부터 탐색하면서 나눌수 있는 부분문자열의 마지막 인덱스(last)를 구한다.

1. 만약 현재 탐색중인 알파벳의 시작인덱스가 last보다 작다면 이 알파벳도 부분문자열에 속해야 한다. 알파벳의 종료 인덱스가 last보다 크다면 갱신한다.
ex) aabbab -> last는 b 인덱스로 갱신

2. 만약 현재 탐색중인 알파벳의 시작인덱스가 last보다 크다면 이 알파벳은 별도의 부분문자열로 나뉠 수 있다. 이때까지 구한 부분문자열의 길이를 정답에 넣고 last를 현재 알파벳의 끝인덱스로 갱신한다.
이를 arr배열의 끝까지 반복한다.
ex) aabb ->  2를 정답에 넣고, last는 b 인덱스로 갱신

시간복잡도는 알파벳 수를 N이라한다면 O(|S| + NlogN + N)이 된다.
O(|S|)는 arr배열을 구하는 것.
O(NlogN)은 정렬. O(N)은 마지막으로 정답을 구하기 위해 arr배열을 탐색할 때 드는 시간복잡도이다.

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/763.%20Partition%20Labels.cpp