오늘 포스팅할 내용은 PCCP 모의고사 문제 중, 유전법칙 문제를 풀이하려고 합니다. 유전법칙 문제는 재밌는 문제였습니다. 긴 시간동안 고민해서 문제를 풀었는데요. 알고리즘 접근법이 잘못되어서 메모리 부족이 발생했습니다. 결국 레퍼런스를 참고해서야 해결할 수 있었습니다. 그래서 이렇게 오답노트 겸 기록하려고 합니다.
부모 유전자에 따라 자식 유전자가 규칙적으로 달라지는 것을 발견하여 재귀로 접근했습니다. 재귀 내의 조건에 따라 다음 세대의 유전 정보를 저장하기 위해 이중 배열을 활용했습니다. 자세하게는 depth에 따라 데이터 길이기 달라지기 때문에 배열 안에는 리스트를 사용했습니다.
재귀 방식으로 순회를 하면 위와 같이 유전자 정보를 배열에 저장합니다. 재귀는 우리가 찾고자하는 위치의 depth에서 종료합니다. 종료가 되면, depth에 해당하는 배열 인덱스에서 찾고자하는 위치의 값을 출력합니다.
위 방식은 단순히 직관적으로 풀이한 것 같습니다. 완전탐색하면서 값을 저장하고 있죠. 해당 문제는 반복되는 규칙을 활용하는 것이 포인트인 것 같습니다.
1-1. 코드
메무리 부족 발생
2. 다른 풀이
1. 유전자의 규칙은 아래와 같습니다. (1) 부모가 "RR"이면, 자식도 "RR" (2) 부모가 "rr"이면, 자식도 "rr" (3) 부모가 "Rr"이면, 자식은 "RR", "Rr", "Rr", "rr" (위치 고정)
2. 한 부모의 자식 유전자는 4개를 갖기 때문에, 자식 유전자의 시작 위치는 부모 유전자 위치 * 4와 같습니다. 3. 그리고 해당 유전자의 정보는 위치에서 4를 나눈 나머지와 동일합니다. 4. 위 규칙에 따라서 자식 유전자를 확인하기 전에 부모 유전자가 RR, rr이면 자식은 무조건 RR,rr 입니다. 5. 스택을 활용하여 유전자들의 위치에서 4로 나눈 나머지를 저장합니다. 6. 스택에서 데이터를 꺼낼 때는 부모부터 꺼내기 때문에 RR, rr 일 경우, 더 이상 탐색할 필요없이 종료합니다. 7. 반대로 데이터를 모두 꺼냈는데도 RR, rr 정보가 없다면 Rr입니다.
2-1. 코드
static String[] arr = {"RR", "Rr", "Rr", "rr"};
public String[] solution(int[][] queries) {
int len = queries.length;
String ans[] = new String[len];
for (int i = 0; i < len; i++) {
int depth = queries[i][0];
int num = queries[i][1] - 1;
Stack<Integer> stk = new Stack<>();
if (depth == 1) {
ans[i] = "Rr";
} else {
while (depth-- > 1) {
stk.push(num % 4);
num /= 4;
}
boolean flag = false;
while (!stk.isEmpty()) {
int pop = stk.pop();
if (pop == 0 || pop == 3) {
ans[i] = arr[pop];
flag = true;
break;
}
}
if(!flag) {
ans[i] = "Rr";
}
}
}
return ans;
}
위 문제를 통해 느낀점은 반복되는 정보가 있을 때는 몫과 나머지를 활용하는 것이 좋다는 것입니다.
