시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 610 6 2 0.855%

문제

규완이는 N개의 순서대로 색칠된 공을 가지고 있다. (색은 영어 대문자로 이루어져 있다.) 당신은 이 공을 가지고 다음과 같은 재미있는 일을 하고자 한다.

1. 가장 많은 개수로 같은 색이 연속된 공을 제거한다.
 2. 만약 가장 많은 개수로 같은 색이 연속된 부분이 여럿 있다면, 그 중에서 맨 앞에 있는 부분을 제거한다.
 3. 1, 2를 공이 모두 제거될 때 까지 반복한다.

이 과정을 반복하던 도중, 규완이는 k 번째 공이 몇 번째 사라질지 궁금해졌다. 규완이를 도와주자.

입력

첫째 줄에는 공의 개수인 N과, 자신이 언제 없어지는지 알고 싶은 공의 번호 k가 주어진다.
  그 다음 줄에는 공의 색이 연속된 N개의 문자열로 주어진다.

출력

그 k번째 공이 사라지는 시행횟수가 몇 번째인지 출력한다.

예제 입력

10 4
AABAABBBCD

예제 출력

3

힌트

0 : AABAABBBCD 1 : AABAACD 2 : BAACD 3 : BCD

출처

  • 문제를 만든 사람: xhark