[Programmers] PCCP 모의고사 1회 3번 - 유전법칙 - Java

문제

https://school.programmers.co.kr/learn/courses/15008/lessons/121685

프로그래머스

 

풀이

완두콩의 세대와 몇번째 완두콩에 대한 정보로 어떤 완두콩인지 알아내는 문제이다.

2세대  

완두콩 그룹별: 1개

완두콩 총개수: 4개

 

3세대

완두콩 그룹별: 4개

완두콩 총개수: 16개

 

그림을 잘 보면 첫번째와 맨끝은 무조건 RR와 rr로 정해지는 것 같다.

Rr에서 후손인 완두콩들을 보면 마찬가지이다.

 

사실 필자는 이 문제를 해결하지 못했었는데, 3세대에서 2번째 3번째 그룹은 RR인지 Rr인지 rr인지 확실하게 알 수 없다.

그리고 1번째 그룹에 속하면 RR, 4번째 그룹에 속하면 rr인 것은 확실하다.

 

2번째 3번째 그룹이면 부모 세대로 가서, 확인을 하면 될 것이고, 계속 부모 세대로 가서 root 완두콩까지 가면 Rr이고,

1번째 그룹 : RR, 4번째 그룹: rr

이다.

 

generation(세대)를 감소시키는 것을 생각했다.

세대의 그룹 별 완두콩의 갯수는 POW(4, 세대 - 2)이다.

 

1. 그룹이 1번째, 4번째면 RR, rr이다 

문제에서는 몫연산을 해야하고, 1번째부터 수를 세고 있기에 -1을 해야한다.

 

2. 2번째, 3번째 그룹이면 그룹별 완두콩의 개수에서 나머지 연산을 한 값을 갱신하면서, 세대를 감소시킨다.

 

3. 반복문을 수행하면서, 세대가 1에 왔으면 Rr이다.

RR, rr은 1 세대로 반복문에서 절대 올 수 없다.

 

소스코드

class Solution {
    public String[] solution(int[][] queries) {
        String[] answer = new String[queries.length];
        
        for (int i = 0; i < queries.length; i++) {
            int generation = queries[i][0];
            int order = queries[i][1] - 1;
            
            String s = "";
            
            while (true) {
                if (generation == 1) {
                    s = "Rr";
                    break;
                }
                
                int genUnit = (int) Math.pow(4, generation - 2);
                int group = order / genUnit;
                
                if (group == 0) {
                    s = "RR";
                    break;
                }

                if (group == 3) {
                    s = "rr";
                    break;
                }
                
                generation -= 1;
                order %= genUnit;
            }
           
            answer[i] = s;
        }
        
        return answer;
    }
}

 

실행결과