import java.util.*;
class Solution {
static String[] arr = {"RR", "Rr", "Rr", "rr"};
public String[] solution(int[][] queries) {
// 부모가 RR이면 나는 RR
// 부모가 rr 이면 나는 rr
// 부모가 Rr이면 나는 % 4 의 값
// 어떻게 부모를 알 수 있을까?
// 4로 계속 나누어 몫이 0일 때까지 나누면 0, 1, 2, 3의 나머지가 나온다
int len = queries.length;
String rst[] = new String[len];
for(int i = 0; i < len; i++) {
int gen = queries[i][0];
int num = queries[i][1] - 1;
Stack<Integer> stk = new Stack<>();
if(gen == 1) {
rst[i] = "Rr";
} else {
while(gen > 1) {
gen--;
stk.push(num % 4);
num /= 4;
}
boolean flag = false;
while(!stk.isEmpty()) {
int pop = stk.pop();
if(pop == 0 || pop == 3) {
rst[i] = arr[pop];
flag = true;
break;
}
}
if(!flag) {
rst[i] = "Rr";
}
}
}
return rst;
}
}
이 문제가 규칙이 있을 것이라고 생각한 이유
유전 형질의 데이터가 너무 많아서 저장할 수 없다.
4^15개
RR에서는 RR이
rr에서는 rr이
결국 조상 중에 하나가 RR, rr이면 나는 무조건 RR, rr이다
하나라도 RR, rr이 없다면 결국 답은 Rr이다
스택으로 첫 조상 부터 저장해주고 꺼내면서 나머지가 0이거나 3이 나온다면 나는 RR or rr이다
마지막까지 나머지가 0이거나 3인 친구가 없다면 Rr이 답인
간단한 문제였다.