문제
법과학 연구소에서는 짧은 연쇄 반복(STR)으로 사람을 비교합니다. STR은 AGAT처럼 짧은 DNA 단위가 연달아 여러 번 나타나는 것입니다. 연구소는 단위마다 서열 전체에서 연속으로 이어진 가장 긴 반복 횟수를 기록합니다. TTAGATAGATAGATCAGATAGAT에서 AGAT는 앞쪽에서 세 번 연달아, 뒤쪽에서 두 번 연달아 나오므로 횟수는 3입니다.
dna_str_count(sequence, repeats) 함수를 구현하세요.
입력
sequence: A, C, G, T로 이루어진 DNA 서열입니다.
repeats: 횟수를 셀 STR 단위들입니다.
출력
repeats와 같은 순서로 단위마다 횟수 하나씩, 즉 연달아 나타나는 가장 많은 반복 횟수를 반환하세요. 한 번도 나오지 않는 단위의 횟수는 0입니다.
제약 조건
0 ≤ sequence의 길이 ≤ 5,000
1 ≤ 단위의 개수 ≤ 10
각 단위는 1~8글자입니다
예시
입력:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
예상 출력:
expected = [3, 1]
입력:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
예상 출력:
std::vector<long long> expected = {3, 1};
입력:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
예상 출력:
long[] expected = new long[] {3, 1};
설명
AGAT는 앞쪽에서 3번, 끝에서는 2번만 연달아 나오므로 3입니다. CA는 한 번 나오므로 1입니다.
입력:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
예상 출력:
expected = [3, 1, 0]
입력:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
예상 출력:
std::vector<long long> expected = {3, 1, 0};
입력:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
예상 출력:
long[] expected = new long[] {3, 1, 0};
설명
AATG는 3번 반복되고 TATC는 1번, GATA는 한 번도 나오지 않으므로 [3, 1, 0]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
시작 위치에서, 다음 조각이 단위와 같은 동안 단위 길이만큼 계속 앞으로 건너뛰세요.
힌트 2
모든 시작 위치를 시도하며 가장 긴 반복을 기억하세요.
힌트 3
한 번도 일치하지 않는 단위는 최고 횟수가 0으로 남습니다.
예상 복잡도
시간 O(n × m × k), 추가 공간 O(m)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.