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

DNA 짧은 연쇄 반복(STR) 세기

각 짧은 연쇄 반복 단위가 DNA 서열에서 연달아 가장 많이 반복되는 횟수를 구합니다.

배우게 될 내용

  • 문자열의 부분 문자열을 패턴과 비교한다
  • 한 위치에서 시작해 연달아 나오는 반복 횟수를 센다
  • 패턴마다 가장 큰 횟수를 기억한다

문제

원문 보기 (영어)

법과학 연구소에서는 짧은 연쇄 반복(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글자입니다

예시

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

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

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

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

다른 사람의 풀이 보기

커뮤니티 솔루션

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