시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 735 20 5 1.534%

문제

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

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

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

입력

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

출력

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

예제 입력

10 4
AABAABBBCD

예제 출력

3

힌트

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

출처

  • 빠진 조건을 찾은 사람: wkd48632
  • 문제를 만든 사람: xhark