[JAVA 자바] 프로그래머스 PCCP 모의고사 3번 유전법칙

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

프로그래머스

재귀로 풀수있는 문제다. 다른풀이보면 스택과 큐로도 풀었던데 스택과 큐로는 잘 모르겠다.

 

재귀로 풀때 핵심

재귀로 풀때 핵심은 주어진 세대와 인덱스[3,25]를 받아서 값이 있는 부모까지 재귀를 타고 부모의 값을 찾았다면 그에 해당하는 자식값을 리턴하는식으로 풀 수 있다.

 

무슨말이냐면 2세대의 인덱스가 1일때는 3을 리턴하고 2세대의 인덱스가 2일때는 4를 리턴한다고 치자.

5세대부터 재귀를 탐색한다. 4세대, 3세대, 2세대에 도달하면 현재 인덱스를 구하고 3을 리턴했다면 3세대는 받은 3을 가지고 자식값을 연산하뒤 4세대로 리턴하고 4세대도 3세대에게 받은 값으로 5세대에게 리턴하는식이다.

 

1 -> 2 -> 3 -> 4 -> 5로 재귀를 탐색한다면 1,2,3,4,5번까지 재귀를 하고 5번이 리턴한 값을 가지고 4번,3번, 2번,1번이 사용한다.

이렇게 설계하려면 함수를 다음과 같이 설계해야한다.

 

public void dfs(int i){
	if(i == 5){
    	//값 연산 후 리턴
        return i
    }

	dfs(i+1); //내 부모가 리턴한 값을 여기서 사용한다.
    //받은 값으로 연산
}

 

이를 기반으로 재귀로 2세대까지 탐색하고 2세대에서 리턴한 값으로 3세대, 4세대, n세대까지 탐색하는식으로 풀 수 있다.

 

class Solution {
    static String[] been = {"rr", "RR", "Rr", "Rr"};
    
    public String[] solution(int[][] queries) {
        String[] answer = new String[queries.length];
        for(int i=0; i<queries.length; i++){
            answer[i] = dfs(queries[i][0], queries[i][1]);
        }

        return answer;
    }
    static String dfs(int gener, int index){
        if(gener == 1) return "Rr";
        if(gener == 2){
            return been[index%4];
        }
        int parentIndex = (int)Math.ceil(index / (double)4);
        String temp = dfs(gener-1, parentIndex);
        if(temp.equals("Rr")) return been[index%4];
        return temp;
    }
}