PCCP 모의고사 유전법칙 (재귀 + 스택)

 오늘은 프로그래머스에서 PCCP라는 코딩테스트 역량 인증 시험이라는게 있길래 궁금해서 들어가봤더니 이 자격증을 따면 취업할 때 우대사항으로 적용되는 회사가 몇군데 있다는걸 알게 되었다. 

 

PCCP 모의고사는 1,2회차가 있었고 한 회차에 4문제가 있다. 그 중 1회차를 풀어보았다. 제한시간은 2시간이였다.

 

  결과 2시간안에는 현실적으로 다 못풀었고 3문제 정도를 2시간 가량 걸려서 풀고 나머지 한문제는 2개경우만 맞고 나머지 다 시간초과 뜨는정도로 풀고 다른사람들의 풀이를 찾아봤다.. 나중에 코테에 자신이 붙으면 한번 응시해봐야겠다.

 

오늘은 PCCP 1회차 중에 3번문제를 풀이해 보겠다. 

 

문제

 문제가 꽤 길다.. 뭐 유전법칙에 대해서 설명하느라고 긴 것 같은데 대충 알고있는 내용이여서 이해가 빨리 됐다. 만약 유전법칙에 대해 모르면 살짝 시간이 걸려 이해할 수도..?있을 것 같다.

결과 적으로 n번째 자손의 p번째 자식이 어떤 형질을 나타내냐 이다.

 

풀이

 처음에는 n이 16까지 길래 그냥 모든 경우의 수를 계산해놓으면 되는 문제인 줄 알고 그렇게 했다.

하지만 4^15+4^14 + ...+4+1 은 계산해보니 몇백억이 넘는다. 즉 메모리 공간이 남아나질 않는다는 것이다. 또 생성하는데 시간또한 100초이상이 걸린다는 것이다. 결국 메모리초과가 났다.

 

 다시 생각을 해보았다. n과 p만으로 어떻게 찾을 수 있을까?

부모와 자식사이의 연관이 있다는 점을 이용해서 내가 부모의 몇번째 자식인지를 첫번째 조상을 만날때 까지 쌓아 놓은다음 쌓아놓은것들을 이용해 하나씩 계산하면 된다는 생각이 들었다.

n 즉 몇번째 자손인지가 나오니 n-1(n<=16)만큼만 쌓으면 되는것이니 시간이나 공간적 제한은 전혀 없을 것이다.

 

그렇다면 어떻게 몇번째 자손인지 알 수 있을까? 그것은 부모는 4개의 자식을 낳는다는 점을 이용했다. 

p를 4로 나눈 나머지가 몇번째 자식인지를 나타내는 것이다. (p%4)

그리고 부모는 n-1 자손들중에 p/4번째 자식이 되는 것이다. ex) p가 16 n 4 ->  부모는 4번째 자식은 0번째

이런식으로 n-1번 실행해 주면 되는 것이다. 다른 사람들 풀이를 보니 Stack안에 몇번째 자손인가를 쌓았는데 나는 그냥 

n-1크기의 배열을 만들어 뒤에서 부터 넣어주고 읽을 땐 앞에서 부터 읽었다.

 코드로 보자

import java.util.*;

class Solution {
    
    static int temp[];
    
    static void find(int n,int p){// ex 3,5 -> 2,4 "RR"
        if(n==0){ // n이 0 즉 첫번째 조상이 되면 쌓기를 멈춘다.
            for(int a : temp){ // 어떻게 쌓여있는지 확인하기 위해 적은 코드
            System.out.print(a+" ");
            }
            System.out.println();
            return;
        }
        temp[n-1]=p%4;
        find(n-1,p/4);
    }
    
    static String ans(){
        int ex=2; //형질 Rr:2 RR:1 rr=3 으로 숫자로 표현했다. 굳이 이럴필요가 없긴하다..ㅎㅎ
        for(int i=0;i<temp.length;i++){ //temp의 길이만큼 실행한다.
            if(ex==2){ // 부모가 Rr
                if(temp[i]==0){ // 첫번째 자식은 RR
                    return "RR"; //다음 자식들은 계속 RR이므로 RR리턴
                }else if(temp[i]==3){ //네번째 자식은 rr
                    return "rr"; //다음 자식들은 계속 rr이므로 rr리턴
                }
            }else if(ex==1){ 
                return "RR"; //다음 자식들은 계속 RR이므로 RR리턴
            }else if(ex==3){ 
                return "rr"; //다음 자식들은 계속 rr이므로 rr리턴
            }
        }
        return "Rr"; //모든 temp를 지나와도 RR과 rr을 만나지 않았으면 Rr리턴
    }
    
    public String[] solution(int[][] queries) {
        
        String[] answer = new String[queries.length];
        for(int i=0;i<queries.length;i++){
            int n=queries[i][0];
            int p=queries[i][1];
            temp=new int[n-1];
            find(n-1,p-1);
            answer[i]=ans();
        }
        return answer;
    }
}

 

피드백

 Stack을 활용했으면 코드가 좀 더 깔끔하지 않았을까 라는 생각과 더불어 문제에 주어진 조건을 읽어보고 시간복잡도 공간복잡도를 잘 생각하여 문제를 풀어야 실제 코딩테스트에서는 문제 풀 시간이 부족하지 않겠다는 생각이 들었다.