모든 챌린지
쉬움 0명 해결 정답률 0%

동전 던지기 연속 기록

동전 던지기 기록에서 앞면의 최장 연속, 뒷면의 최장 연속, 연속 구간의 개수를 구합니다.

배우게 될 내용

  • 수열을 가장 긴 연속 구간들로 나눈다
  • 값마다 가장 긴 연속 구간을 추적한다
  • 연속 구간의 개수를 센다

문제

원문 보기 (영어)

확률 실험실에서 동전을 여러 번 던지고 결과를 H(앞면)와 T(뒷면)로 된 문자열로 적습니다. 연속 구간이란 같은 결과가 연달아 나온 가장 긴 묶음이며, HHTHHH의 연속 구간은 HH, T, HHH입니다. 학생들은 무작위 기록에서 가장 긴 연속 구간이 생각보다 길다는 데 자주 놀라기 때문에, 실험실에서는 이 값을 측정합니다.

coin_toss_streaks(tosses) 함수를 구현하세요.

입력

tosses: H와 T로만 이루어진, 순서대로의 결과입니다.

출력

[longest_heads, longest_tails, streaks], 즉 앞면 최장 연속 길이, 뒷면 최장 연속 길이(한 번도 나오지 않았으면 0), 연속 구간의 전체 개수를 반환하세요.

제약 조건

0 ≤ tosses의 길이 ≤ 100,000

예시

예시 1
입력:
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개입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.