[Greedy] 하나의 문자로 통일하기

예제) 주어진 문자열을 수정하여 하나의 문자로만 구성된 문자열을 만드려고 할 때, 최소로 수행되는 수정 횟수를 구하시오. ( 연속적인 문자는 하나의 문자로 통일 가능하다. )

 

AABACCBABA

 

위 문자열을 AAAAAAAAAA 나 BBBBBBBBBB나 CCCCCCCCCC로 바꾸라는 말이다. 수정횟수를 최소로 하려면 가장 자주 등장하는 문자를 제외한 나머지 문자를 수정해야한다. ( Greedy 알고리즘 )

 

알고리즘 

1) 포인터로 문자열을 검사해서 문자별 등장횟수를 카운트한다. 

2) 동일한 문자가 연속되면 카운트하지 않는다. 

3) 등장 횟수가 많은 문자를 제외한 두 문자의 등장횟수 합이 최소 수정횟수이다. 

 

 

 

A가 등장했다. 현재 문자는 A로 입력되고 A 등장횟수는 1 올라간다.

 

 

 

 

A가 연속해서 등장했다. 현재문자와 동일하므로 등장횟수를 카운트하지 않는다. 

 

 

 

 

B가 등장했다. 현재문자를 B로 바꾸고 B의 등장횟수를 1 올린다.

 

 

 

 

A가 다시 등장했다. 현재문자를 A로 바꾸고 A 등장횟수를 1 올린다. 이를 끝까지 반복해보자. 

 

 

A는 4번, B는 3번, C는 1번 등장했다. 

 

고로, B와 C를 A로 4번 수정하면 최소한의 횟수로 동일한 문자를 가진 문자열로 수정할 수 있다. 

 

 

---

 

참고자료

2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성