[프로그래머스] 유전 법칙 (PCCP 모의고사 1-3)

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

프로그래머스

 

4진법에서 아이디어를 얻어야 하는 문제이다.
다만, 나머지 0을 처리하기가 어렵기 때문에 잘 생각해야 한다.

하위 세대를 선택하는 것은 4로 나눈 나머지, 윗 세대롤 보는 것은 4로 나눈 몫이다.
다만, 몇 번째인지를 계산하는 것이므로, 4로 나눈 몫을 올리는 것이중요하다 (ceil 사용)
맨 윗 세대까지 올라가야 하는데, 그 도중에 몫이 0으로 떨어지는 경우가 존재할 것이다. 그 경우는 맨 왼쪽으로 붙을거기에, 왼쪽으로 보낸다.

RR : 1, Rr : 2, 3 rr : 4

맨 마지막 세대를 보기 전에 (즉 두개 전이다.)  1, 4가 발생할 경우 RR, rr가  확정된다. 여러개의 1, 4가 발생할 수 있으나 맨 위에서 따라 내려오면서 1, 4로 가면 확정이므로 이를 고려하자. 그것이 아닐 경우 마지막을 보고 결정해야 한다.

아, 이 방법은 한 가지 문제가 있다.
맨 처음  [1, 1] 에 대해서는 초기값을 알 수가 없다.! 두 개 전이라는 것을 고려할 수 없으니까. 애초 뿌리를 고려하지 않고 나눈거다.  [1, 1]은 따로처리하자. 그냥 "Rr"이다.

 

import math
def solution(queries):
    # 간단한 사진법 문제로 추정됨.
    # RR, Rr, Rr, rr 이고 RR이나 rr일 경우는 확정되니까. 따라가면서 경우를 잡게 하자.
    # 즉 나머지 4의 올림셈에 해당된다.  그리고  세대 -1 만큼만 하면 됨 이를.
    
    answer = []
    for cur_q in queries:
        gen, seq = cur_q
        # 4로 나누는 나머지의 경우 초기 값을 알 수 없다.
        # 초기값은 따로 채워줘야 한다.
        if cur_q == [1, 1]:
            answer.append("Rr")
        else:
            # track에 루트를 담고 뒤집자.
            track = []
            for _ in range(gen, 1, -1):
                # 나머지가 0일 경우 4번으로 처리
                track.append(seq % 4 if seq % 4 != 0 else 4)
                # 몫이 0일 경우, 채워야 하는 루트는 1로 채워야 한다.
                seq = math.ceil(seq / 4 if seq / 4 > 0 else 1)
            track = track[::-1]
            for i in range(len(track)):
                if i < len(track) - 1:
                    # 최종 단계에 오기전에 1이나 4가 발견되면 RR, rr로 확정된다.
                    # 순서대로 봐야 하므로 이렇게 한다.
                    if track[i] == 1 :
                        answer.append('RR')
                        break
                    elif track[i] == 4:
                        answer.append('rr')
                        break
                else:
                    if track[i] == 1:
                        answer.append('RR')
                    elif track[i] == 4:
                        answer.append('rr')
                    else:
                        answer.append('Rr')
    return answer