티바이트

출처 

Koreatech OnlineJudge(링크)


문제이해

각 테스트케이스마다 문자열이 한 줄씩 주어진다.

문자열은 R, G, B 3가지 문자로 이루어져 있으며 각 문자마다 

일렬로 배치되어 있는 공의 색깔을 나타낸다.

한 턴에 맨 앞 혹은 맨 뒤의 공 하나만 제거할 수 있을 때

한 가지 색만 남기려면 최소 몇 개의 공을 제거해야 하는지 구하는 문제이다.


문제접근

dequeue 같은 자료구조가 연상되는 문제이지만

몇 가지 경우를 생각해 보면, 연속된 색의 최대길이를 구하는 간단한 문제라는 것을 알 수 있다.

문제의 조건에 따르면, 마지막에는 항상 연속된 구간만 남게 되기 때문이다.


구현

문자열을 선형탐색하며 가장 긴 연속색의 길이를 구한다. (O(n))


실행결과



코드 (컴파일러 : GNU C++11)

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1028/1028.cpp


 


댓글을 다는 공간입니다. (로그인하지 않아도 댓글을 남길 수 있습니다.)



게시판 목록은 좌측상단에 있습니다.

Statistics Graph