[PCCP 모의고사] 유전법칙

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이 답인
간단한 문제였다.