코드
1차 시도
시간 복잡도: O(N * M) -> 시간초과
// you can use includes, for example:
// #include <algorithm>
#include <string>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
// write your code in C++14 (g++ 6.2.0)
vector<int> answer;
int memo[27] ={0,};
memo['A'-'A'] = 1;
memo['C'-'A'] = 2;
memo['G'-'A'] = 3;
memo['T'-'A'] = 4;
for(int i=0;i<P.size();i++) {
string str = S.substr(P[i],Q[i]-P[i]+1);
int min = 999;
for(int j=0;j<str.length();j++) {
min = min > str[j]-'A' ? str[j]-'A' : min;
}
answer.push_back(memo[min]);
}
return answer;
}시간 초과 나올 걸 예상했지만 한번 시도해본 풀이이다. 중간에 memo[27]은 그냥 if문 4개 쓰기 싫어서 작성한 코드이다...ㅎ
로직은 그냥 substr을 사용해서 유전을 나누고 for문을 돌면서 min인지 다 비교를 해줬다. 역시 시간 초과가 나왔다.
2차 시도
시간복잡도: O(N + M) -> 통과했으나 테스트케이스가 못 거른 거 같다.
// you can use includes, for example:
// #include <algorithm>
#include <string>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
// write your code in C++14 (g++ 6.2.0)
vector<int> answer;
vector<vector<int>> memo;
vector<int> A, C, G, T;
for(int i=0;i<S.length();i++) {
if(S[i] == 'A') {
A.push_back(i);
} else if(S[i] == 'C') {
C.push_back(i);
} else if(S[i] == 'G') {
G.push_back(i);
} else if(S[i] == 'T') {
T.push_back(i);
}
}
memo.push_back(A);
memo.push_back(C);
memo.push_back(G);
memo.push_back(T);
for(int i=0;i<P.size();i++) {
for(int j=0;j<4;j++) {
bool flag = false;
for(int k=0;k<memo[j].size();k++) {
if(memo[j][k] >= P[i] && memo[j][k] <= Q[i])
{
flag = true;
answer.push_back(j+1);
break;
}
}
if(flag) break;
}
}
return answer;
}ACGT가 나온 index들을 저장한 다음 A -> C -> G -> T 순서로 for문을 돌면서 존재하면 answer에 넣고 break해줬다.
통과는 했지만 만약에 AAAAAAAAAAAA~T이런식으로 마지막이 T이고 P, Q가 마지막 글자를 가리킨다면 P.size() x S.length()이므로 O(N*M)이 나와서 통과를 못 할 거 같은데 그런 테스트 케이스가 없었는 거 같다.
3차 시도
아마 O(N+M)일 것이다.
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
// write your code in C++14 (g++ 6.2.0)
vector<int> answer;
int path[4][S.length()] = {0,};
if(S[0] == 'A') path[0][0] = 1;
else if(S[0] == 'C') path[1][0] = 1;
else if(S[0] == 'G') path[2][0] = 1;
else if(S[0] == 'T') path[3][0] = 1;
for(int i=1;i<S.length();i++) {
if(S[i] == 'A') {
path[0][i] = path[0][i-1]+1;
path[1][i] = path[1][i-1];
path[2][i] = path[2][i-1];
path[3][i] = path[3][i-1];
}
else if(S[i] == 'C') {
path[0][i] = path[0][i-1];
path[1][i] = path[1][i-1]+1;
path[2][i] = path[2][i-1];
path[3][i] = path[3][i-1];
}
else if(S[i] == 'G') {
path[0][i] = path[0][i-1];
path[1][i] = path[1][i-1];
path[2][i] = path[2][i-1]+1;
path[3][i] = path[3][i-1];
}
else if(S[i] == 'T') {
path[0][i] = path[0][i-1];
path[1][i] = path[1][i-1];
path[2][i] = path[2][i-1];
path[3][i] = path[3][i-1]+1;
}
}
for(int i=0;i<P.size();i++) {
for(int p=0;p<4;p++) {
int start = P[i] == 0 ? 0 : path[p][P[i]-1];
// cout << start << " " << path[p][Q[i]] << endl;
if(path[p][Q[i]] - start > 0) {
// cout << p << endl;
answer.push_back(p+1);
break;
}
}
}
return answer;
}계속 맞왜틀(맞는데 왜 틀림)이었는데 prefix로 해결할 방법이 안 떠올라서 참고해서 풀었다.
먼저 내 얘기를 하기 전에 풀이를 작성해보겠다. 예시는 문제에 나온 CAGCCTA로 들겠다.
첫글자를 확인해서 먼저 첫 글자의 path를 기억하는 배열을 1로 만들어줬다.
그러면 path[1][0] = 1이 저장된다.
그리고 나서 한글자씩 확인하면서 개수를 세려줬다.
이렇게 하면 다음과 같은 결과가 나온다.
path[0] = [0, 1, 1, 1, 1, 1, 2]
path[1] = [1, 1, 1, 2, 2, 2, 2]
path[2] = [0, 0, 1, 1, 1, 1, 1]
path[3] = [0, 0, 0, 0, 0, 1, 1]
이걸 어떻게 활용할 수 있냐면
path[0]을 보면 1번 index에 처음 나오고 그 뒤에 안 나오다가 6번 index에 나왔다.
즉, 2~5의 부분 배열에는 A가 없다는 것을 알 수 있다.
배열의 index가 p, q로 주어졌다고 했을 때 path[0][q] - path[0][p]의 값을 확인하면 개수를 구할 수 있다.
문제의 예시로 좀 더 살펴보면 P[0] = 2 Q[0] = 4가 처음에 주어진다.
2~4번째는 GCC로 A가 없음을 알 수 있는데 path[0][4]와 path[0][2]는 둘다 1로 같다. 따라서 0이므로 A가 없음을 알 수 있다.
// i는 P, Q의 배열 index, j는 path의 배열 index
즉, 위를 수식화 하면 path[j][Q[i]] - path[j][P[i]]로 계산할 수 있다.
참고로 P[i]가 0이면 P[i]-1이 -1이므로 처음에 한번 삼항연산자를 활용해 처리해줬다.
이런식으로 path[0]~path[3]까지 보다가 1이상이 나오면 그 값을 저장하면 된다. 작은 순(A->C->G->T)으로 확인하니까 1이상 값이 나올 때 바로 break해줘도 된다.
밑은 이 문제를 풀면서 발생한 이슈이다.
이거때문에 시간을 너무 많이썼다... 위에 시간복잡도를 아마라고 생각한 이유는 통과를 못해서이다. 근데 맞았다고 나는 생각한다(?). 무슨 소린가 싶겠지만 다른 사람들 풀이를 참고해서 그대로 cpp로 바꾼건데 틀렸다고 나와서였다.
여러 케이스에서 틀렸는데 확인해보기 위해 결과 페이지에서 틀렸다고 나오는 single 케이스를 테스트 케이스를 작성했는데 어이가 없었다.
(중간에 start가 위의 코드와 다르게 삼항 연산자가 아닌 이유는 저기서 문제가 나오나해서 테스트해봐서이다.)
위 사진을 보면 ['T', [0], [0]]일 때 return value가 3이 나온다.
4가 나와야하는 데 이상해서 디버깅을 위해 cout을 사용해봤다.
결과는 아래와 같다.
??? 갑자기 4가 나왔다... cout만 넣었는데 왜인지 모르겠지만 4가 나왔다.
이해가 안돼서 결국 codility에 문의 메일을 남겼는데 현재 아래와 같은 답변을 받았다.
Hello,
We have forwarded this to our senior technical team to look into and they will be in touch after reviewing the details.
Kind regards,
Ajas
Codility Support
senior technical팀이 살펴봐야 문제가 해결될 거 같은데 갑자기 든 생각은 코딜리티 서비스로 코딩테스트를 보는 기업들이 있는데 과연 이런 문제가 없었을까라는 의문이 들었다...(못 풀어서 떨어졌을 가능성이 크지만)
풀이 및 소감
먼가 문제의 난이도가 올라가면서 문제 이해하기도 어려워지는 거 같다...(영어를 못해서인가...)ㅠㅠ 다른 사람들의 풀이를 봐도 한번에 이해가 안 됐어서 여러 풀이를 봤었다... 이걸 prefix로 어떻게 풀지했는데 역시 해결책은 있었다...
쨌든 처음에 prefix로 해결을 못해서 다른 방식들로 시도하고 코딜리티의 오류(아마)로 시간도 날리고 애를 먹은 문제였다ㅠㅠ 추후 코딜리티 측에서 답변이 오면 내용을 추가해봐야겠다.
참고 사이트
- [Codility] GenomicRangeQuery 문제 풀이 - cheolhojung님 블로그
- [Codility(코딜리티)]Lesson5. GenomicRangeQuery(100%) - 잭코딩 스토리님 블로그
