설명
입력
출력
예시 입력
예시 출력
JavaScript
복사
JavaScript
복사
풀이 과정
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
String[] input = br.readLine().split(" ");
int k = Integer.parseInt(input[0]);
String dna = input[1];
System.out.println(findKMCS(dna, k));
}
}
private static int findKMCS(String dna, int k) {
HashMap<Long, Integer> map = new HashMap<>();
long[] count = new long[4]; // 'A', 'G', 'T', 'C'의 빈도 수
for (int i = 0; i < k; i++) {
count[charToIndex(dna.charAt(i))]++;
}
long hash = hash(count);
map.put(hash, 1);
int maxFrequency = 1;
for (int i = k; i < dna.length(); i++) {
count[charToIndex(dna.charAt(i - k))]--;
count[charToIndex(dna.charAt(i))]++;
hash = hash(count);
int frequency = map.getOrDefault(hash, 0) + 1;
map.put(hash, frequency);
maxFrequency = Math.max(maxFrequency, frequency);
}
return maxFrequency;
}
private static int charToIndex(char c) {
switch (c) {
case 'A': return 0;
case 'G': return 1;
case 'T': return 2;
case 'C': return 3;
default: return -1; // 이 경우는 발생하지 않음
}
}
// 간단한 해시 함수로 'A', 'G', 'T', 'C'의 빈도 수를 하나의 해시값으로 변환
private static long hash(long[] count) {
return count[0] + 10007 * count[1] + 1000000007 * count[2] + 10000000000037L * count[3];
}
}
JavaScript
복사
오류 코드
