문제 설명
주어진 문자열에서 특정 문자가 최소 n개 이상 들어있는지 확인하는 문제로 처음에는 한칸씩 밀면서 문자열을 확인하는 방식으로 접근했다.
for(int i=0; i < S - P + 1; i++){
String checkString = dna.subString(i, i + P);
...
}이와 같이 문자열을 subString으로 추출하고 특정 로직을 수행하는 방식으로 해당 문자열이 비밀번호로 사용할 문자가 적합한지 판단했다. 반복문을 사용해서 확인하면 시간초과가 발생할 것을 우려해
checkString.length() - checkString.replace("A", " ").length()와 같이 추출한 전체 길이에서 확인하려는 문자를 공백으로 바꾼뒤 빼서 확인했지만 시간초과가 발생하는 것을 알 수 있었는데 이유는 다음과 같다.
public String replace(CharSequence target, CharSequence replacement) {
String trgtStr = target.toString();
String replStr = replacement.toString();
int thisLen = this.length();
int trgtLen = trgtStr.length();
int replLen = replStr.length();
if (trgtLen > 0) {
if (trgtLen == 1 && replLen == 1) {
return this.replace(trgtStr.charAt(0), replStr.charAt(0));
} else {
boolean thisIsLatin1 = this.isLatin1();
boolean trgtIsLatin1 = trgtStr.isLatin1();
boolean replIsLatin1 = replStr.isLatin1();
String ret = thisIsLatin1 && trgtIsLatin1 && replIsLatin1 ? StringLatin1.replace(this.value, thisLen, trgtStr.value, trgtLen, replStr.value, replLen) : StringUTF16.replace(this.value, thisLen, thisIsLatin1, trgtStr.value, trgtLen, trgtIsLatin1, replStr.value, replLen, replIsLatin1);
return ret != null ? ret : this;
} } else {
int resultLen;
try {
resultLen = Math.addExact(thisLen, Math.multiplyExact(Math.addExact(thisLen, 1), replLen));
} catch (ArithmeticException var12) {
throw new OutOfMemoryError("Required length exceeds implementation limit");
}
StringBuilder sb = new StringBuilder(resultLen);
sb.append(replStr);
for(int i = 0; i < thisLen; ++i) {
sb.append(this.charAt(i)).append(replStr);
}
return sb.toString();
}}해당 코드는 replace 내장 함수로 동작 과정을 보면 마지막에 반복문을 사용해 대체한 String을 다시 할당해서 반환하는 것을 볼 수 있다. 그렇기 때문에 코드상에서 반복문을 사용하는 것과 크게 다를 것이 없다.
for(int i = 0; i < thisLen; ++i) {
sb.append(this.charAt(i)).append(replStr);
}
return sb.toString(); 정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
int S = Integer.parseInt(firstLine[0]);
int P = Integer.parseInt(firstLine[1]);
String dna = br.readLine();
int result = 0;
String[] thirdLine = br.readLine().split(" ");
int[] minCount = new int[4];
for (int i = 0; i < 4; i++) {
minCount[i] = Integer.parseInt(thirdLine[i]);
}
result = answer(dna, minCount, S, P);
System.out.println(result);
br.close();
}
static int answer(String dna, int[] minCount, int S, int P) {
int result = 0;
int[] checkCount = new int[4];
boolean check;
char before = ' ';
for (int i = 0; i < S - P + 1; i++) {
if (i == 0) {
String checkString = dna.substring(i, i + P);
checkCount = initCheck(checkString);
before = checkString.charAt(i);
} else {
char after = dna.charAt(i + P - 1);
checkCount = updateCheck(before, after, checkCount);
before = dna.charAt(i);
}
check = checkString(minCount, checkCount);
if (check) {
result++;
}
}
return result;
}
static int[] initCheck(String checkString) {
int[] result = new int[4];
result[0] = checkString.length() - checkString.replace("A", "").length();
result[1] = checkString.length() - checkString.replace("C", "").length();
result[2] = checkString.length() - checkString.replace("G", "").length();
result[3] = checkString.length() - checkString.replace("T", "").length();
return result;
}
static int[] updateCheck(char before, char after, int[] checkCount) {
if (before == 'A') {
checkCount[0]--;
} else if (before == 'C') {
checkCount[1]--;
} else if (before == 'G') {
checkCount[2]--;
} else {
checkCount[3]--;
}
if (after == 'A') {
checkCount[0]++;
} else if (after == 'C') {
checkCount[1]++;
} else if (after == 'G') {
checkCount[2]++;
} else {
checkCount[3]++;
}
return checkCount;
}
static boolean checkString(int[] minCount, int[] checkCount) {
if (checkCount[0] < minCount[0]) {
return false;
}
if (checkCount[1] < minCount[1]) {
return false;
}
if (checkCount[2] < minCount[2]) {
return false;
}
if (checkCount[3] < minCount[3]) {
return false;
}
return true;
}
}메소드를 분리해서 코드가 길지만 동작 과정은 매우 단순하다.
1. 문자열 추출 및 checkCount
가장 처음에는 비밀번호로 사용할 만큼 길이의 문자열을 처음 인덱스부터 추출해서 checkCount를 만들어준다. 여기서 checkCount는 현재 문자열에 포함된 단어를 check하는 배열로 해당 배열로 최소 포함 개수 배열과 비교하며 비밀번호로 적절한지 판단한다.
2. 추가 , 삭제되는 문자를 checkCount에 반영
이후 새로 확인하는 문자가 "AT"라고 할 때 G를 before, T를 After로 설정해 before에 해당하는 count를 1 감소 , after 해당하는 count를 1 증가하여 checkCount를 업데이트 한다.
해당 과정을 반복하며 다음과 같은 checkString을 수행해주며 비밀번호로 적절한 문자열을 판단한다.
static boolean checkString(int[] minCount, int[] checkCount) {
if (checkCount[0] < minCount[0]) {
return false;
}
if (checkCount[1] < minCount[1]) {
return false;
}
if (checkCount[2] < minCount[2]) {
return false;
}
if (checkCount[3] < minCount[3]) {
return false;
}
return true;
}정리
일반적으로 1억번의 연산이 1초에 진행된다고 가정하고 시간초과가 발생하지 않게 코드를 구현하는 방법에 대해서 좀 더 고민해야겠다.🙃
