[LeetCode- Part. 4] 1. N일 후 감옥 ## (+ 재귀함수, Arrays.toString, 삼항연산자)

https://leetcode.com/problems/prison-cells-after-n-days/submissions/

Prison Cells After N Days - LeetCode

 

1. 2중 for문 -> 타임리밋 발생

2. 재귀 이용

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        //감옥이 사용될경우 1, 비어있을 경우 0
        
        //양쪽의 감옥이 모두 사용할 경우나 둘 다 비어있을 경우 1
        //그외엔 모두 비어있게 된다.
        //처음과 마지막은 양쪽의 감옥이 존재하지 않는다.
        
        //0,1,0,1,1,0,0,1
        int m=cells.length;
        
        
        for(int i=0;i<n;i++){
            ArrayList<Integer> toOne = new ArrayList<>();
            ArrayList<Integer> toZero = new ArrayList<>();
            
            for(int j=0; j<m;j++){
                if(j==0 || j==m-1){
                    if(cells[j]==1) cells[j]=0;
                    continue;
                }
                if(cells[j-1]==cells[j+1]){
                    toOne.add(j);
                }
                else toZero.add(j);
            }
            
            for(int x : toOne) cells[x]=1;
            for(int x: toZero) cells[x]=0;
        }
        
        return cells;
    }
}

 

2. 재귀 이용

class Solution {

    public int[] prisonAfterNDays(int[] cells, int N) {
        if(cells==null || cells.length==0 || N<=0){
            return cells;
        }
        //1.ds
        Set<String> set = new HashSet<>();
        int cycle=0;
        boolean isCycle=false;
        //2. loop
        for(int i=0;i<N;i++){
            int[] next = nextDay(cells);
            
            //사이클 찾기위해 set에 string으로 넣는다.
            String key=Arrays.toString(next);
            
            if(!set.contains(key)) {
                set.add(key);
                    cycle++; 
            }else{
                //같을 경우
                isCycle=true;
                break;
            }
            //다음날 감옥을 대입
            cells=next;
        }
        //사이클 발견시
        if(isCycle){
            //N%cnt를 구한다
            N=N%cycle;
            for(int i=0;i<N;i++){
                cells=nextDay(cells);
            }
        }
        return cells;
    }
    
    private int[] nextDay(int[] cells){
        int[] nums=new int[cells.length];
        
        //다음날 바꿀 감옥 생성
        for(int i=1;i<cells.length-1;i++){
            nums[i]=cells[i-1] == cells[i+1] ? 1:0;
        }
        return nums;
    }
}

 

 

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        //int배열을 set에 넣을 때에는 Arrays.toString()을 이용해 배열을 문자열로 변환 후 넣는다.
        
        //1.ds
        boolean flag= false;
        int cnt=0;
        Set<String> set = new HashSet<>();
        
        //2. loop
        for(int i=0;i<n; i++){
            int[] next =makeCells(cells);
            
            //존재했던 감옥인지 체크 -> String이므로 반드시 String으로 체크
            if(set.contains(Arrays.toString(next))){
                flag=true;
                break;
            }
            
            //존재하지 않았다면, 추가
            set.add(Arrays.toString(next));
            cnt++;
            
            cells=next;
        }
        
        
        if(flag){
            n=n%cnt;
            for(int i=0;i<n;i++){
                cells = makeCells(cells);
            }

        }
        return cells;
    }
    
    //감옥을 새로 생성
    private int[] makeCells(int[] cells){
        int[] nums = new int[cells.length];
        for(int i=1;i<cells.length-1;i++){
           nums[i]=cells[i+1]==cells[i-1]?1:0;
        }
        return nums;
    }
}

 

---

1. 새로운 감옥 생성

(1) 1번칸부터 len-1칸까지만 확인

2. 중복 확인

3. 중복아니면 Set에 넣고 cells=next;

4.중복이면 break해, 사이클을 이용해 리턴

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        int len=cells.length;
        int[] answer=new int[len];
        Set<String> set = new HashSet<>();
        int cnt=0;
        boolean flag=false;
        for(int i=0;i<n;i++){
            
            int[] next=makeInt(cells, len);
            if(set.contains(Arrays.toString(next))) {
                flag=true;
                break;
            }
            set.add(Arrays.toString(next));
            cnt++;
            
            cells=next;
        }
        if(flag){
            n=n%cnt;
            for(int i=0;i<n;i++) {
               int[]next= makeInt(cells, len);
                cells=next;
            }
        }
        //makeInt
        //cycle
        return cells;
    }
    private int[] makeInt(int[] cells, int len){
        //양옆이 같으면 1, 다르면 0
        int[] nums = new int[len];
        for(int i=1;i<len-1; i++){
           nums[i]=cells[i+1]==cells[i-1]?1:0;
        }
        return nums;
    } 
}