1025: 단색이 좋아좋아

Link : judge.koreatech.ac.kr/problem.php?id=1025

---

1. 문제

• 한 줄에 빨강, 파랑, 초록 색상의 공들이 섞여 있습니다.
  각 공의 색깔은 순서대로 R, B, G 로 표현합니다.
  여러분은 한 턴에 제일 앞의 공 혹은 제일 뒤의 공을 제거할 수 있습니다.
  한 색깔의 공만 남기기 위해서는 최소 몇 번의 턴이 필요할까요?

 

---

2. 문제의 조건

• R, G, B로만 이루어져 있다.
• 1 <= T <= 100
• 1 <= len <= 10

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한 1초에 100개의 TestCase에 10개의 문자열길이니 총 1000개니 약 O(N^2.66) 시간 이내에 풀면 될 것 같습니다.

 

• 아이디어
  
  R, G, B중 가장 길게 연결되어있는 길이를 알아낸 후 전체 길이에서 가장 긴 부분만 빼면 정답이므로 O(N)의 시간복잡도가 나올 것입니다.

 

---

4. 풀이 방법

• 1부터 len(arr)까지 탐색을한다.
• 만약 arr[i]와 arr[i-1]가 같을경우 pres(현재길이)를 하나씩 증가 시킵니다.
• 만약 두개가 다르다면, 이어져있지 않은 상태이므로 pres와 max를 비교하여 최대값을 갱신하고 pres를 1로 바꾸어놓습니다.
• 탐색이 끝난 후 pres와 max를 한번 더 갱신하여 전체길이에서 가장 긴 부분(max)를 빼주면 답이 나옵니다.

 

---

5. 소스코드

• cjw-git.tistory.com/33

 

---

 

cjw.git@gmail.com