색칠된 공들
시간 제한2초메모리 제한128 MB
같은 색 공이 연속된 구간 중 가장 긴 것(동일하면 가장 왼쪽)을 반복해서 제거하면서 인접 구간을 합치는 과정을 시뮬레이션해 k번째 공이 몇 번째 연산에서 제거되는지 구하는 문제입니다.
문제
규완이는 왼쪽부터 오른쪽까지 일렬로 놓인 N개의 공을 가지고 있다. 각 공의 색은 영어 대문자 하나로 표시된다.
공이 모두 없어질 때까지 다음 과정을 반복한다.
- 현재 남아 있는 공들 중에서 같은 색이 연속된 가장 긴 묶음을 찾는다.
- 그런 묶음이 여러 개라면, 가장 왼쪽에 있는 묶음을 선택한다.
- 선택한 묶음의 공을 모두 제거한다.
처음에 왼쪽에서 k번째였던 공이 몇 번째 시행에서 제거되는지 구하라.
입력
첫째 줄에 공의 개수 N과 제거되는 시점을 알고 싶은 공의 번호 k가 주어진다.
둘째 줄에 길이가 N인 문자열이 주어진다. 문자열의 각 문자는 해당 위치 공의 색을 나타내는 영어 대문자이다.
제한: 1 ≤ k ≤ N ≤ 10,000,000
출력
처음에 왼쪽에서 k번째였던 공이 제거되는 시행 번호를 출력한다.
힌트
공을 제거한 뒤 양쪽에 남은 묶음이 같은 색이면 두 묶음은 서로 붙어 하나의 더 긴 묶음이 된다. 이후 시행에서는 이렇게 합쳐진 묶음의 길이를 기준으로 다시 가장 긴 묶음을 고른다.