[프로그래머스] PCCP 모의고사 1회 3번 유전법칙 - 파이썬/재귀

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

재귀

def gen(gen_list,n,a):
    ans_list = []

    for i in gen_list:
        if i == 'RR':
            ans_list.append('RR')
            ans_list.append('RR')
            ans_list.append('RR')
            ans_list.append('RR')
        elif i=='Rr':
            ans_list.append('RR')
            ans_list.append('Rr')
            ans_list.append('Rr')
            ans_list.append('rr')
        else:
            ans_list.append('rr')
            ans_list.append('rr')
            ans_list.append('rr')
            ans_list.append('rr')

    n -= 1
    if n==0:
        ans = ans_list[a-1]
        return ans
    else:
        return gen(ans_list,n,a)


def solution(queries):
    answer = []
    for i in queries:
        n = i[0]-1
        a = i[1]
        answer.append(gen(['Rr'],n,a))
    
    
    return answer

재귀를 사용하여 푸는 문제같다.

조건 그대로 구현해서 풀었다.

그런데 테스트 케이스는 통과하지만 시간 초과로 오답이 나왔다.

구현

def solution(queries):
    answer = []


    for i in queries:
        idx_list = []
        n = i[0] # 세대
        idx = i[1] # 위치

        idx = idx-1

        while n>1:

            nam = idx%4
            idx_list.append(nam)
            idx = idx//4
            n -= 1

        check = False

        while len(idx_list)>0:
            num = idx_list.pop()

            if num == 0:
                check = True
                answer.append('RR')
                break

            elif num == 3:
                check = True
                answer.append('rr')
                break

        if not check:
            answer.append('Rr')

    return answer


print(solution([[3, 1], [2, 3], [3, 9]]))

해당 세대의 위치를 4로 나누면 나머지에 따라 세대에서 몇번째 형제인지를 알 수 있다.

계속 나누면서 한번이라도 RR이나 rr을 만난다면 RR 이나 rr이고, 한번도 안만나면 Rr을 출력해준다.