Greedy 예제(6) Partition Labels

 

예제 ) 주어진 문자열을 파티션으로 나누려 한다. 파티션에 포함된 문자는 다른 파티션에서 발견되면 안 될 때, 파티션 개수의 최솟값을 구하라. 

 

 

 c가 파티션1과 파티션2에서 발견되므로 이와 같은 분류는 안 된다. 

 

 

알고리즘 

 

Greedy한 접근법을 이용해보자. ( 현재값을 기준으로 최적의 선택을 하는 방법 )

 

1) 문자열의 문자를 좌측부터 하나씩 포인터로 지목한다. ( 현재 포인터 )

2) 현재 포인터가 가리키는 문자의 마지막 포인터가 현재 포인터라면 파티션을 분리한다.

( 현재포인터 = 마지막 포인터 )

 

그럼 마지막 포인터 정보를 알아야한다. 반복문을 돌려 문자열의 문자를 하나씩 체크한다. 문자의 마지막 인덱스가 무엇인지 HashMap 자료구조에 저장한다.

 

 

 

 

 

이제 Greedy한 접근법을 다시 해보자. 

 

 

 

 

 

현재 포인터가 0이고 

a의 마지막 포인터가 2이니 

포인터를 넘긴다. 

 

 

 

새로운 문자가 등장하면

현재 문자는 바뀐다.

 

현재 포인터가 1이고

c의 마지막 포인터가 3이니

포인터를 넘긴다.

 

 

 

a는 이미 나왔으므로

현재문자는 c로 유지된다. 

 

현재 포인터는 2이고 

c의 마지막 포인터는 3이므로

포인터를 넘긴다. 

 

 

 

현재 포인터와 마지막 포인터가 동일하다.

파티션을 나누어준다. 

 

이와 같은 원리로 

계속 진행해준다. 

 

 

파티션은 3개로 나뉘어진다.

 

 

---

 

참고영상