인증된 문제 실버 V

Duck Duck Duck! (2)

출제자 Moondev · 티어 투표 0명
로그인하고 제출
시간 제한메모리 제한채점 방식맞힌 사람제출한 사람정답 비율
1.0 초 256 MB 정답 코드 + 생성기 · 전부 맞아야 100점 1명 2명 25%

문제

오리를 좋아하는 덕덕이는 알파벳이 적힌 카드 N장을 일렬로 늘어놓았습니다. 덕덕이는 카드를 왼쪽부터 순서대로 한 장씩 확인하며 "Duck"이라는 단어를 만들어 보려고 합니다. 단어는 반드시 앞쪽부터 'D' -> 'u' -> 'c' -> 'k' 순서로 등장해야 완성할 수 있습니다. 즉, 'D'를 찾기 전에는 다음 글자를 찾을 수 없고, 'D'를 찾은 후에만 'u'를, 'u'를 찾은 후에만 'c'를, 'c'를 찾은 후에만 'k'를 찾을 수 있습니다. 'k'까지 찾아 단어를 하나 완성했다면, 그 이후의 카드들로 다시 'D'부터 찾아 새로운 단어를 만들어야 합니다. 한 번 지나친 카드는 다시 되돌아가서 사용할 수 없으며, 단어를 만드는 데 사용된 카드도 다시 쓸 수 없습니다. 덕덕이가 왼쪽부터 카드를 확인할 때 완성할 수 있는 "Duck" 단어의 최대 개수를 구하는 프로그램을 작성하세요.

입력

첫째 줄에 카드의 개수 N (1 ≤ N ≤ 1,000,000)이 주어집니다. 둘째 줄에 알파벳 대문자로 이루어진 길이 N의 문자열이 주어집니다.

출력

만들 수 있는 "Duck" 단어의 최대 개수를 출력합니다.
Moondev님의 문제를 변형함