[PCCP 모의고사#1] 유전법칙 (스택)

문제 설명

멘델은 완두콩을 이용하여 7년간 실험한 결과, 다음과 같은 특별한 법칙을 발견하였습니다.

1. 둥근 완두 순종(RR)을 자가 수분, 즉 같은 유전자끼리 교배할 경우, 다음 세대에 둥근 완두 순종 형질만 나타난다.
2. 주름진 완두 순종(rr)을 자가 수분할 경우, 다음 세대에 주름진 완두 순종 형질만 나타난다.
3. 두 순종을 교배한 잡종(Rr)을 자가 수분할 경우, 다음 세대의 형질은 RR:Rr:rr=1:2:1의 비율로 나타난다. (아래 그림 참조)

멘델의 법칙을 공부한 진송이는, 직접 완두콩의 자가 수분 실험을 진행했습니다. 진송이의 실험에서 완두콩 한 개를 자가 수분한 결과는 다음과 같습니다.

1. 각 완두콩은 자가 수분해서 정확히 4개의 완두콩 후손을 남긴다.
2. 잡종 완두콩(Rr)은 자가 수분해서 첫째는 RR, 둘째와 셋째는 Rr, 넷째는 rr 형질의 후손을 남긴다.
3. 순종 완두콩(RR, rr)은 자가 수분해서 자신과 같은 형질의 후손을 남긴다.

잡종 완두콩(Rr) 1대부터 시작한 가계도로 그려보면 그림 2와 같습니다.

진송이는 이러한 완두콩의 자가 수분 실험 결과를 정리하고 싶어합니다. 하지만, 세대를 거듭할수록, 완두콩의 수가 너무 많아져 모든 가계도를 기록하기 어려워졌습니다. 진송이는 가계도를 전부 기록하는 것 대신, 완두콩의 세대와 해당 세대에서 몇 번째 개체인지를 알면 형질을 바로 계산하는 프로그램을 만들려 합니다.

각 세대에서 맨 왼쪽 개체부터 첫 번째, 두 번째, 세 번째, ...개체로 나타냅니다. 예를 들어 그림 2에서 2세대의 네 번째 개체의 형질은 "rr"이며, 3세대의 9번째 개체의 형질은 "RR"입니다.

형질을 알고 싶은 완두콩의 세대를 나타내는 정수 n과, 해당 완두콩이 세대 내에서 몇 번째 개체인지를 나타내는 정수 p가 2차원 정수 배열 queries의 원소로 주어집니다. queries에 담긴 순서대로 n세대의 p 번째 개체의 형질을 문자열 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ queries의 길이(쿼리의 개수) ≤ 5
• queries의 원소는 [n, p] 형태입니다.
  • 1 ≤ n ≤ 16
  • 1 ≤ p ≤ 4n-1

입출력 예

queries	result
[[3, 5]]	["RR"]
[[3, 8], [2, 2]]	["rr", "Rr"]
[[3, 1], [2, 3], [3, 9]]	["RR", "Rr", "RR"]
[[4, 26]]	["Rr"]

입출력 예 설명

입출력 예 #1

• 본문의 가계도를 참고하면 3세대의 5번째 개체의 형질이 RR임을 알 수 있습니다.

입출력 예 #2

• 본문의 가계도를 참고하면 3세대의 8번째 개체의 형질이 rr임을 알 수 있습니다.
• 본문의 가계도를 참고하면 2세대의 2번째 개체의 형질이 Rr임을 알 수 있습니다.

입출력 예 #3

• 본문의 가계도를 참고하면 3세대의 1번째 개체의 형질이 RR임을 알 수 있습니다.
• 본문의 가계도를 참고하면 2세대의 3번째 개체의 형질이 Rr임을 알 수 있습니다.
• 본문의 가계도를 참고하면 3세대의 9번째 개체의 형질이 RR임을 알 수 있습니다.

입출력 예 #4

• 4세대의 26번째 개체는 3세대의 7번째 개체(Rr)의 둘째 후손으로, 형질은 Rr이 됩니다.

풀이

• gen = 1일 때, Rr
• gen = 2일 때, 셀프폴리네이션[개체번호-1]
  • 셀프폴리네이션 = [RR,Rr,Rr,rr]
• gen = 3일 때, 3세대 셀프폴리네이션[개체번호-1]
  • 셀프폴리네이션 = [RR,RR,RR,RR] [RR,Rr,Rr,rr] [RR,Rr,Rr,rr] [rr,rr,rr,rr]
• 셀프폴리네이션을 미리 만들면...
  • 1<= n <= 16, 4의 16제곱....
  • 1<= p <= 4**(n-1) ㅎㅎㅎ
  • 미리 못 만듬. 규칙을 알아내야 하네...
• 규칙은 심플해보인다.
  • gen > 2일 때, (개체번호-1)를 4로 나눈 몫으로 이전 세대의 셀프폴리네이션 배열의 유전자를 알 수 있음.
    • 예) 3세대, 4번 개체는 RR임.
      • 개체번호-1 (4-1) / 4 = 0
      • 2세대 0번 개체 = RR
  • 4세대, 개체번호 64
    • 3세대, 15 (63/4 = 15.75)
      • 2세대, 3.75 (2세대 3은 rr)
  • 4세대, 개체번호 32
    • 31/4 = 7.75 (3세대, 7)
      • 7/4 = 1.75 (2세대, 1) = Rr
• 근데 RR, Rr, rR, rr이 아니라 RR, Rr, Rr, rr이라서 뭔가 삽질했다.
  • 재귀호출로 해보려다가 안되서 스택과 while 문으로... 대부분 이렇게 푼 것 같다.

def solution(queries):
    answer = []
    
    def find(gen, individual):
        stack = []

        while gen > 1:
            gen -= 1
            individual, mod = divmod(individual,4)
            stack.append(mod)

        while len(stack) > 0:
            mod = stack.pop()
            if mod == 0:
                return "RR"
            if mod == 3:
                return "rr"
        return "Rr"

    for q in queries:
        g, i = q[0],q[1]-1
        answer.append(find(g, i))
    
    return answer

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.1MB)
테스트 3 〉	통과 (0.01ms, 10.4MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.02ms, 10.1MB)
테스트 7 〉	통과 (0.02ms, 10.2MB)
테스트 8 〉	통과 (0.02ms, 10.2MB)
테스트 9 〉	통과 (0.02ms, 9.93MB)
테스트 10 〉	통과 (0.02ms, 10.1MB)

• 고수의 풀이
  • 와 신박하다.

def solution(queries):
    cdict = ['RR', 'Rr', 'Rr', 'rr']
    answer = []
    for q in queries:
        if q[0] == 1:
            answer.append('Rr')
        val = q[1]-1
        for i in range(q[0], 1, -1):
            mok = val// (4**(i-2))
            if mok == 0:
                answer.append('RR')
                break
            elif mok == 3:
                answer.append('rr')
                break
            if i == 2:
                answer.append(cdict[mok])
                break
            val %= (4**(i-2))
    return answer

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.02ms, 10.2MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.01ms, 10.3MB)
테스트 9 〉	통과 (0.01ms, 10.1MB)
테스트 10 〉	통과 (0.01ms, 10.2MB)