[Java] 프로그래머스 유전법칙

 

문제

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

프로그래머스

알아야 할 개념

• 재귀함수 호출 dfs 

풀이

재귀 함수 dfs 탐색을 주어진 조건을 고려했을때, 

• 탐색 레벨의 최대값은 16이다. 
• bfs로 주어진 index까지 브르투 포스 하면 4억번 이상의 연산으로 tle 를 마주하게 된다
• 특정 위치만 찾는법은 없을까? 

라는 생각이 들었다.

 

풀이는 다음과 같다.

1. 우선 주어진 조건을 재귀함수로 받는다.
2. Level이 1이면 "Rr" 리턴.
3. Level이 2이면 (문제에서 2nd generation) 해당 문자열 리턴.
4. Level > 2 일 경우
   1. 주어진 K Level에서 2 Level 까지 탐색한다.
   2. K .. 2 까지 탐색하면서 index 정보를 리스트에 담는다. 
   3.     2 Level으로 올라왔을 경우, 4 로 나눈 나머지가 0 또는 3이면 해당 문자열 리턴한다. (RR, 또는 rr 인 경우니깐)
   4.        나머지가 1 또는 2이면  Rr 임으로 알고리즘 4-2 의 리스트 전부  알고리즘 4-3을 이용하여 탐색한다.

모든 경우를 탐색하는 것이 아닌 Level 을 이용해 탐색을 하기 때문에 Time Limit Exceptions 가 나지 않는다. 

 return getStr(gen-1, index, cur/4, prev); // Level을 1 줄인다.

참고

level 16 번째 의 index 가 주어졌을때, 의 탐색을 그려보았다.

• 파란색 start 지점으로 level 2까지 탐색한다. 
• Level 2 부터는 prevList 에 있는 것들을 뽑아가면서, 탈출 조건에 걸리는지 확인한다. 

 

코드

import java.util.*;

class Solution {
    String [] info = {"RR", "Rr", "Rr", "rr"};//Level 2 였을때
    
    public String[] solution(int[][] queries) {
        List<String> l = new ArrayList<>();
        
        for(int x[] : queries){
            if(x[0] == 1)l.add("Rr");
            else l.add(getStr(x[0],x[1]-1, x[1]-1, new LinkedList<Integer>()));
        }
        return l.stream().map(x -> x).toArray(String[]::new);
    }
    //세대, 번쨰
    public String getStr(int gen,int index, int cur, LinkedList<Integer> prev){
        if(gen == 1)return "Rr";
        else if(gen == 2){
            if(cur == 0 || cur == 3)return info[cur];
            else{
                while(!prev.isEmpty()){
                    int nextIndex = prev.pollLast();
                    if(nextIndex % 4 == 0 || nextIndex % 4 == 3 || nextIndex == index){
                        prev.clear();
                        return info[nextIndex % 4];
                    }
                }
            }
        }
        //이전 인덱스 추가
        prev.add(cur);
        return getStr(gen-1, index, cur/4, prev);
    }
    
}