PCCP 모의고사 1회 : 유전법칙

 

문제분석

 

멘델의 유전법칙을 이용하여  n세대의 X번 개체의 유전자를 반환하는 문제다.

 

이 문제에선 1세대가 무조건 Rr이다.

 

 

멘델의 유전법칙에따라 2세대부터  RR일경우, 자식은 모두 RR 

 

Rr일경우,  1:2:1 비율로 RR Rr rr 이 생성,

 

rr일경우  모든 자식이 rr이 생성된다.

 

 

멘델의 유전법칙에따라서 N 세대에 X번째 의 나올걸 유츄해야한다.

 

유전 세대는  이전세대의 4배씩 생성된다.

 

N세대에 X번째의 정확한 자식의 유전자를 알기위해선  N-1세대의 부모의 여부를 알아야한다.

 

그 여부를 Stack을 이용해서 구현했다.

 

Stack을사용해  X번째를 4로나눈 나머지를 사용하여 부모의 유전자를 추정해간다.

 

 

문제는 1번부터세고,  컴퓨터는 0번부터세기에,  둘의 시작번호를 통일시키기 좀 애를 먹었다.

문제풀이

import java.util.*;
class Solution {
    public String[] solution(int[][] queries) {
        String[] answer = new String[queries.length];
        
        //멘델 Rr의 분열규칙을 저장
        String[] arr = new String[]{"RR","Rr","Rr","rr"};
        
        int idx=0;
        for(int[] query:queries){
           
            int level=query[0];
            int count = query[1]-1;
            
            Stack<Integer> stack =new Stack<>();
            
            // 빠르게구할수있는 Level2까진 예외처리
            if(level==1){
                answer[idx]="Rr";
                idx++;
                continue;
            }
            if(level==2){
                answer[idx]=arr[count];
                idx++;
                continue;
            }
            
            //Level3부턴 로직을 사용함
            while(level!=1){ 
                int namuge=count%4;
                count/=4;
 
                level-=1;
                stack.push(namuge);
 
            }
            
            while(!stack.isEmpty()){
                
                String current= arr[stack.pop()];
                
                if(current.equals("RR")){
                    answer[idx]=current;
                    break;
                }
                else if(current.equals("rr")){
                    answer[idx]=current;
                    break;
                }
              
                
                answer[idx]=current;
            }
            
            
            
            idx++;
         
        }
        
        return answer;
    }
}