문제
주사위 시뮬레이터가 육면체 주사위를 굴린 결과를 모두 리스트에 기록합니다. 연속 구간이란 같은 눈이 연달아 나온 묶음이며, 한 번만 나온 눈도 길이 1인 연속 구간입니다. 가장 긴 연속 구간을 찾으세요. 가장 긴 길이의 구간이 여러 개라면 가장 먼저 시작하는 구간을 답합니다.
longest_run_of_rolls(rolls) 함수를 구현하세요.
입력
rolls: 굴린 순서대로의 결과이며, 각 값은 1부터 6까지입니다.
출력
[start, length], 즉 가장 긴 연속 구간이 시작하는 인덱스(0부터 시작)와 그 길이를 반환하세요. 리스트가 비어 있으면 [-1, 0]을 반환합니다.
제약 조건
0 ≤ 굴린 횟수 ≤ 10,000
1 ≤ 눈 ≤ 6
예시
입력:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]
예상 출력:
expected = [4, 3]
입력:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};
예상 출력:
std::vector<long long> expected = {4, 3};
입력:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};
예상 출력:
long[] expected = new long[] {4, 3};
설명
인덱스 4에서 시작하는 6 세 개가 4 두 개보다 길므로 [4, 3]입니다.
입력:
rolls = [5, 5, 2, 2, 3]
예상 출력:
expected = [0, 2]
입력:
std::vector<long long> rolls = {5, 5, 2, 2, 3};
예상 출력:
std::vector<long long> expected = {0, 2};
입력:
long[] rolls = new long[] {5, 5, 2, 2, 3};
예상 출력:
long[] expected = new long[] {0, 2};
설명
두 구간 모두 길이가 2이고, 5의 구간이 인덱스 0에서 먼저 시작하므로 [0, 2]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
현재 연속 구간이 어디서 시작했는지 기억하세요.
힌트 2
값이 바뀌거나 리스트가 끝나면, 끝난 구간을 최적 구간과 비교하세요.
힌트 3
새 구간이 엄밀히 더 길 때만 최적 구간을 바꾸세요.
예상 복잡도
시간 O(n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.