출처
Koreatech OnlineJudge(링크)
문제이해
각 테스트케이스마다 문자열이 한 줄씩 주어진다.
문자열은 R, G, B 3가지 문자로 이루어져 있으며 각 문자마다
일렬로 배치되어 있는 공의 색깔을 나타낸다.
한 턴에 맨 앞 혹은 맨 뒤의 공 하나만 제거할 수 있을 때
한 가지 색만 남기려면 최소 몇 개의 공을 제거해야 하는지 구하는 문제이다.
문제접근
dequeue 같은 자료구조가 연상되는 문제이지만
몇 가지 경우를 생각해 보면, 연속된 색의 최대길이를 구하는 간단한 문제라는 것을 알 수 있다.
문제의 조건에 따르면, 마지막에는 항상 연속된 구간만 남게 되기 때문이다.
구현
문자열을 선형탐색하며 가장 긴 연속색의 길이를 구한다. (O(n))
실행결과
코드 (컴파일러 : GNU C++11)
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1028/1028.cpp