모든 챌린지
보통 0명 해결 정답률 0%

주사위 최장 연속 구간

같은 눈이 연달아 나온 가장 긴 구간의 시작 위치와 길이를 구합니다.

배우게 될 내용

  • 같은 값이 이어지는 구간이 끝나는 곳을 찾는다
  • 최적 구간의 시작 위치와 길이를 기억한다
  • 동률이면 먼저 나온 구간을 택한다

문제

원문 보기 (영어)

주사위 시뮬레이터가 육면체 주사위를 굴린 결과를 모두 리스트에 기록합니다. 연속 구간이란 같은 눈이 연달아 나온 묶음이며, 한 번만 나온 눈도 길이 1인 연속 구간입니다. 가장 긴 연속 구간을 찾으세요. 가장 긴 길이의 구간이 여러 개라면 가장 먼저 시작하는 구간을 답합니다.

longest_run_of_rolls(rolls) 함수를 구현하세요.

입력

rolls: 굴린 순서대로의 결과이며, 각 값은 1부터 6까지입니다.

출력

[start, length], 즉 가장 긴 연속 구간이 시작하는 인덱스(0부터 시작)와 그 길이를 반환하세요. 리스트가 비어 있으면 [-1, 0]을 반환합니다.

제약 조건

0 ≤ 굴린 횟수 ≤ 10,000

1 ≤ 눈 ≤ 6

예시

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

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

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

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

다른 사람의 풀이 보기

커뮤니티 솔루션

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