문제
확률 실험실에서 동전을 여러 번 던지고 결과를 H(앞면)와 T(뒷면)로 된 문자열로 적습니다. 연속 구간이란 같은 결과가 연달아 나온 가장 긴 묶음이며, HHTHHH의 연속 구간은 HH, T, HHH입니다. 학생들은 무작위 기록에서 가장 긴 연속 구간이 생각보다 길다는 데 자주 놀라기 때문에, 실험실에서는 이 값을 측정합니다.
coin_toss_streaks(tosses) 함수를 구현하세요.
입력
tosses: H와 T로만 이루어진, 순서대로의 결과입니다.
출력
[longest_heads, longest_tails, streaks], 즉 앞면 최장 연속 길이, 뒷면 최장 연속 길이(한 번도 나오지 않았으면 0), 연속 구간의 전체 개수를 반환하세요.
제약 조건
0 ≤ tosses의 길이 ≤ 100,000
예시
입력:
tosses = "HHTHHH"
예상 출력:
expected = [3, 1, 3]
입력:
std::string tosses = "HHTHHH";
예상 출력:
std::vector<long long> expected = {3, 1, 3};
입력:
string tosses = "HHTHHH";
예상 출력:
long[] expected = new long[] {3, 1, 3};
설명
연속 구간은 HH, T, HHH이므로 앞면 최장 연속은 3, 뒷면 최장 연속은 1이고, 연속 구간은 3개입니다.
입력:
tosses = "TTTT"
예상 출력:
expected = [0, 4, 1]
입력:
std::string tosses = "TTTT";
예상 출력:
std::vector<long long> expected = {0, 4, 1};
입력:
string tosses = "TTTT";
예상 출력:
long[] expected = new long[] {0, 4, 1};
설명
앞면은 한 번도 나오지 않았으므로 최장 연속은 0이고, 길이 4인 뒷면 연속 구간이 하나 있으므로 [0, 4, 1]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
새 연속 구간은 인덱스 0에서, 그리고 직전 결과와 다른 결과가 나오는 곳에서 시작합니다.
힌트 2
앞면과 뒷면의 최장 길이를 각각 따로 기억하세요.
힌트 3
빈 문자열에는 연속 구간이 하나도 없습니다.
예상 복잡도
시간 O(n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.