[프로그래머스/LV3] [PCCP 모의고사 3] 3번 - 재귀 (Java)

[PCCP 모의고사 #1] 3번 - 유전법칙

🙋‍♂️ 들어가며

재귀를 통해 조상을 구하며 검증하는 방식이다.

이 사진을 보면 부모를 역으로 거슬러 올라가 찾으면서 자녀의 형질을 찾는 것이다.

여기서 부모가 “RR” 이면 자녀는 자동으로 “RR”

또는 부모가 “rr” 이면 자녀는 자동으로 “rr”

그외 잡종 “Rr”이면 조건문에 따라 나누면 되겠다, 나머지를 활용해서 말이다 (0,1,2,3)

위 사진은 4세대까지 구한 그림인데, 여기서 빨간색 표시한것들을 검증해볼까?

다음 테스트 케이스들을 검증해보자

tc-1

n = 4
p = 5

부모 세대를 찾자 세대를 거슬러 올라가면서 p/=4

3세대로 거슬러 올라가고, 2세대로 거슬러 올라가면 그때 prev_p = 0이 되고

그때 나머지 연산을 통해 “RR”을 구해주면 되겠다

부모가 “RR”로 판명났으니 자녀는 자동으로 “RR”

tc-2

n = 4
p = 19

3세대로 거슬러 올라가면 prev_p = 4

2세대로 가면 prev_p = 0이 되고, 이때 나머지 연산을 통해 자동으로 “RR”

부모가 “RR”로 판명났으니 자녀는 자동으로 “RR”

tc-3

n = 4
p = 20

3세대로 거슬러 올라가면 prev_p = 5

2세대로 가면 prev_p = 1 이때 나머지 연산을 통해 부모는 “Rr”

부모가 “Rr”인 상태에서 p에 대한 나머지 연산으로 0이 나오고 자녀는 “RR”로 판정

tc-4

n = 4
p = 22

3세대로 거슬러 올라가면 prev_p = 5

2세대로 거슬러 올라가면 prev_p = 1, 이때 나머지 연산을 통해 부모는 “Rr”

부모가 “Rr”인 상태에서 p에 대한 나머지 연산으로 2가 나오고 자녀는 “Rr”로 판명

tc-5

n = 4
p = 23

3세대로 거슬러 올라가면 prev_p = 5

2세대로 거슬러 올라가면 prev_p = 1, 이때 나머지 연산을 통해 부모는 “Rr”

부모가 “Rr”인 상태에서 p에 대한 나머지 연산으로 3이 나오고 자녀는 “rr”로 판명

tc-6

n = 4
p = 63

3세대로 거슬러 올라가면 prev_p = 15

2세대로 거슬러 올라가면 prev_p = 3, 이때 나머지 연산을 통해 부모는 “rr”

부모가 “rr”라서 자녀도 자동으로 “rr”판명

✅ 정답 코드

class Solution {
    public String[] solution(int[][] queries) {
        int N = queries.length;
        String[] answer = new String[N];
        for (int i = 0; i < N; i++) {
            int[] cur_pos = queries[i];
            int cur_generation = cur_pos[0];
            int cur_p = cur_pos[1];
            
            // 1. 형질찾기
            String cur_genotype = lets_find_genotype(cur_generation, cur_p-1);
            answer[i] = cur_genotype;
        }
        return answer;
    }
    
    
    // 2. 형질찾기 함수
    static String lets_find_genotype(int cur_generation, int cur_p) {
        // 2-1. 1세대라면?
        if (cur_generation == 1) return "Rr";
        
        // 2-2. 2세대 이상이라면?
        int parent_p = cur_p / 4;
        String parent_genotype = lets_find_genotype(cur_generation-1, parent_p);
        
        // 2-3. 부모 종류 판별을 위한 조건문
        String res = "";
        int p_type = cur_p % 4;
        if (p_type == 0) res = "RR";
        else if (p_type == 1) res = "Rr";
        else if (p_type == 2) res = "Rr";
        else if (p_type == 3) res = "rr";
        
        // 2-4. 만약 부모가 순종이라면? -> 볼 필요도 없다
        if (parent_genotype == "RR") return "RR";
        if (parent_genotype == "rr") return "rr";
        
        // 2-5. 그 외 부모가 잡종(Rr)일때
        return res;
    }
    
    
    
}