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

 

문제 : PCCP 모의고사 - 유전법칙

바로가기

 

문제 설명

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

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

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

각 완두콩은 자가 수분해서 정확히 4개의 완두콩 후손을 남긴다.
잡종 완두콩(Rr)은 자가 수분해서 첫째는 RR, 둘째와 셋째는 Rr, 넷째는 rr 형질의 후손을 남긴다.
순종 완두콩(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

 

입출력 예

입력	출력
[[3, 5]]	["RR"]
[[3, 8], [2, 2]]	["rr", "Rr"]
[[3, 1], [2, 3], [3, 9]]	["RR", "Rr", "RR"]
[[4, 26]]	["Rr"]

 

해답 및 해설

여러가지 방법으로 풀 수 있어서 좋았던 문제. 특히 이진 연산으로 푼 해법은 흥미로웠다.

파이썬 (Python)

스택을 이용한 방법

def get_gene(pose):
    n, p = pose
    stack = []
    
    p -= 1
    while n>1:
        stack.append(p%4)
        n -= 1
        p //= 4
    
    while len(stack) > 0:
        num = stack.pop()
        if num == 0: return 'RR'
        if num == 3: return 'rr'
    return 'Rr'

def solution(queries):
    return [*map(get_gene, queries)]

 순서 p를 4로 나누면 형제 중 몇 번째였는지 알 수 있습니다. 또 4로 나눈 몫은 부모 세대에서의 순서가 되지요. 이제 p를 계속 4로 나눠주며 나머지를 저장하게 되면, 모든 부모 세대들이 몇 번째 자식이었는지를 가장 꼭대기까지 저장해줍시다.

 

 그 후 스택 방식으로 가장 오래된 세대부터 꺼내서 분석합니다. Rr의 자식 중 가장 첫번째 자식은 RR이고, 네 번째 자식은 rr입니다. 그리고 RR와 rr의 자식들은 항상 형질이 자기 자신과 같게 나옵니다. 그러니 중간에 한 번이라도 첫 번째나 네 번째가 나오면 해당 형질을 리턴해줍시다. 만약 이 두 가지 경우에 해당하지 않는다면 남은 형질은 Rr이 됩니다. 

 

재귀를 이용한 방법

def get_gene(pose):
    n, p = pose
    if n == 1: return 'Rr'
    
    mother_gene = get_gene((n-1, (p-1)//4+1))
    case = ('RR','Rr','Rr','rr')
    
    if mother_gene == 'Rr': return case[p%4-1]
    else: return mother_gene

def solution(queries):
    return [*map(get_gene, queries)]

위에서 살펴본 규칙에 따라 부모의 형질을 재귀로 불러오는 방법입니다. 부모세대의 형질이 'Rr'이면 자식 순서에 따라 리턴값이 정해지고, 아니라면 부모와 똑같은 값을 리턴 값으로 가집니다.

 

이진 연산을 이용한 방법

def get_gene(pose):
    n, p = pose
    p -= 1
    
    bound = 1<<((n-1)<<1)
    xand_p = (p+bound) ^ (~(p>>1)+bound)
    mask = (bound-1)// 3
    
    check_gene = xand_p & mask

    if check_gene == 0: return 'Rr'
    
    i = 1
    while check_gene>1:
        check_gene >>= 1
        i <<= 1
    
    if p & i:
        return 'rr'
    else:
        return 'RR'
    

def solution(queries):
    return [*map(get_gene, queries)]

 이 글의 댓글에서 영감을 받아 작성하였지만, 아직 완벽하게 이해하지는 못한 방법입니다. 반복문 없이 할 수 있는 방법은 아직 못 찾았네요ㅠㅠ

 

n=5, p`=46 => p`=00/10/11/10

 

 우선 p에서 1을 뺀 값을 p`라 이름 붙이고, 이를  이진수로 변환해봅시다. 그러면 두 자리씩 끊은 값이 부모 세대들의 위치가 됩니다. 00이면 가장 왼쪽, 11이면 가장 오른쪽이 되지요. 그럼 여기서 가장 왼쪽부터 살펴봐 00이나 11이 언제 나오는지 살펴보면 됩니다. 위 예시의 경우는 가장 먼 조상의 위치가 00이니, 그 조상의 형질은 'RR'일 것입니다. 그리고 RR의 자식들은 모두 RR이니 해당 예시의 형질도 RR이 될 것입니다.

 

bound + p`= 1/00/10/11/10

bound + (p`>>1) = 1/00/01/01/11

bound+p` ^ (bound+~(p`>>1)) = 1/11/00/01/10

 

여기서 00와 11의 위치를 파악하려면, p`와 p`>>1 값을 XAND 연산을 해줍시다. 그러면 홀수번째 자리수를 봤을 때, 00과 11처럼 같은 경우는 1이 되고, 01이나 10처럼 서로 다른 경우는 0이 됩니다. 그러면 이제 홀수번째 자리에서 가장 왼쪽부터 봤을 때 1이 나오는 경우를 찾으면 되죠. bound를 붙여준 이유는 파이썬에서는 비트가 정해져있지 않기 때문에 앞쪽의 00을 계산하지 않게 되는데, 이를 막기 위함입니다. bound는 n-1에 2를 곱한 값만큼 1을 왼쪽으로 쉬프트해서 만들어줍니다.

 

xand_p = 1/11/00/01/10

mask = 01/01/01/01

xand_p&mask = 01/00/01/00

 

이제 짝수번째 자릿수만 쉽게 보기 위해 마스크를 씌워줍시다. 아까 만들어둔 bound에서 1을 빼서 1로만 이루어진 수를 만든 다음, 3으로 나누면 홀수번째만 1인 수가 나오게 됩니다. 이걸 아까까지 계산했던 수하고 AND 연산을 해주면,  홀수번째에 1인 경우만 남게되지요. 

 

마지막에 나온 수가 0인 경우는 한번도 00이나 11이 나오지 않았다는 것이므로, 형질이 Rr이 됩니다. 0이 아니라면 반복문을 이용하여 가장 왼쪽의 1을 찾아줍시다. 그리고 원래 수 p`에서 해당 위치에 있는 수가 1이면 11이라는 뜻이므로 'rr', 0이라면 00이라는 뜻이므로 'RR'이 됩니다!

 

자바스크립트 (Javascript)

function getGene(pose) {
    let [n, p] = pose
    let stack = []
    
    p--
    while (n>1) {
        stack.push(p%4)
        n--
        p = parseInt(p/4)
    }
    
    while (stack.length > 0) {
        num = stack.pop()
        if (num == 0) return 'RR'
        if (num == 3) return 'rr'
    }
    return 'Rr'
}

function solution(queries) {
    return queries.map(getGene)
}

스택을 이용한 방법