[Array] Partition Labels

특정 string이 input으로 들어왔을 때, 최대한 하나의 part로 보이게끔 string을 나누면 몇개가 되느냐를 묻는 문제이다.

다시말해, 각 part에 포함된 각각의 string이 겹치지 않도록 part를 나누는 방법을 구하라는 뜻.

이때 리턴값은 각 part의 갯수로 구성된 배열이 된다.

 

이렇게 part에 대한 maximum을 찾는 문제는 greedy algorithm의 활용으로 귀결된다.

greedy algorithm은 원소들을 순회하되, 각 순회 시점에서 global solution만을 고려하며 매 순회마다 비교하는 방식이다

따라서 한번의 순회로 도출된 global solution이 모든 경우에 대한 global solution인 경우에 적용될 수 있다.

위와 같은 문제도 이러한 유형에 해당되는데, 이렇게 input이 continous하고 max를 구하는 문제라면 greedy를 먼저 생각해봄직 하다.

 

 

우선 index가 되는 array와 map을 만든다.

Map의 경우 set을 이용해 원소를 insert하고 get을 이용해 read한다

input string을 모두 순회하며 각각의 원소가 등장한 위치를 insert하였다.

set은 동일한 key에 대해 마지막 value를 overwrite하므로, 해당 원소가 등장한 마지막 위치가 indexMap에 저장 될 것이다.

 

이제 다시 순회를 하며 indexMap을 이용해 partition을 나눌것이다.

이 과정에서 two pointer algorithm을 사용한다.

배열 순회시 가리키는 원소를 두개로 하고, 두개를 연산한 값을 고려하며 솔루션을 찾아가는 방법이다.

 

예를들어 내림차순으로 구성된 10개의 원소를 가진 배열에 대해 두개 원소를 합해 40이 되는 수를 찾는다고 하는 문제의 경우를 생각해보자.

이 케이스에서 3번,10번 원소의 합이 40보다 작다면, 1번-10번, 2번-10번의 조합을 확인할 필요가 없다

이렇게 계산을 위한 과정을 줄이기 위해 two pointer algorithm을 사용한다.

 

해당 문제도 마찬가지이다.

start, end 포인터 두개를 두고 input string을 다시 순회한다.

이때 end를 part의 최대 indexMap value를 가진 원소로 업데이트해주면, partition을 하는 시점에서 끊어진다

 

실제 예시 input인 'ababcbacadefegdehijhklij'로 예를 들어보자

하나의 part에서 가장 큰 indexMap value를 가진 a가 part가 끝나는 지점이 된다.

따라서 Loop의 조건에 end로 설정된 지점에 오는 경우, part의 갯수를 array에 push해준다

이 과정에서 Math.max를 이용하는 방식이 greedy algorithm을 활용한 것이다.

 

이때 갯수는 end-start+1이 될것이다.

그리고 다음 start 지점을 설정해주고 다음 part에 대한 Loop를 순회한다.

 

최종적으로 indexArray를 리턴하면 된다.