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

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

프로그래머스

 

처음 풀었던 방법

# 규칙 : 1/4는 "RR" 2/4는 Rrchild 반복 1/4는 "rr"

def solution(queries):
    answer = []
    
    for n, p in queries:
        childs = 4**(n-1) # 총 자식의 수
        quarter = int(childs/4)
        if n == 1:
            answer.append("Rr")
        elif n == 2:
            if p == 1:
                answer.append("RR")
            elif p == 4:
                answer.append("rr")
            else:
                answer.append("Rr")
        # n이 2보다 클 경우 
        elif 1 <= p <= quarter: # 1/4
            answer.append("RR")
        elif quarter < p <= quarter*3: # 2/4
            isRr = True
            cntRr = 0
            cntNRr = 0
            if p == (quarter + 1):
                answer.append("RR")
            elif p == quarter*3:
                answer.append("rr")
            for i in range(quarter+2, quarter*3):
                if isRr:
                    cntRr += 1
                    if i == p:
                        answer.append("Rr")
                        break
                    elif cntRr == 1:
                        continue
                    else:
                        cntRr = 0
                        isRr = False
                else:
                    cntNRr += 1
                    if (i%2 == 0):
                        if i == p:
                            answer.append("rr")
                            break
                    else:
                        if i == p:
                            answer.append("RR")
                            break
                    if cntNRr == 1:
                        continue
                    else:
                        cntNRr = 0
                        isRr = True
        else:
            anser.append("rr")
                            

    return answer

테케는 맞는데 채점했을 때 정확성이 20%밖에 나오지 않았다.

 

정답 참고

https://programming4myself.tistory.com/88

def solution(queries):
    answer = []
    for n, p in queries:
        stack = []  
    
        p -= 1
        while n>1:
            stack.append(p%4)
            n -= 1
            p //= 4
            
        flag = False
        while len(stack) > 0:
            num = stack.pop()
            if num == 0: 
                answer.append("RR")
                flag = True
                break
            if num == 3: 
                answer.append("rr")
                flag = True
                break
            
        if not flag:
            answer.append("Rr")

    return answer

 

다양한 풀이 방법이 있는데 "스택"을 이용한 방법을 참고했다.

4로 나누면 몫으로 부모 세대에서의 순서가 된다. (0~3)은 첫 번째 (4~7)은 두 번째 ... 

그렇게 첫 번째 while문으로 부모 세대들이 몇 번째 자식이었는지 가장 꼭대기까지 저장 !

 

두 번째 while문에서 0이면 RR 3이면 rr을 저장해주면 된다.

2, 3번째 (1, 2) 더라도 0, 3의 자식일 수 있기 때문에 모든 스택 (모든 부모의 이력)을 꺼내서 확인해줘야 한다.

만약 모든 부모가 0 혹은 3이 아닐 경우 Rr이 answer에 들어가게 된다.

 

 

이 문제의 핵심은 "4로 나눠 부모 세대의 순서 구하기"였는데 이걸 떠올리지 못했다.

무지성 코딩을 하기 전에 더 간단한 규칙을 찾는 습관을 갖자 !

다른 방법도 복습하기 ✅