[Algorithm] 6월12일 알고리즘 연습 (프로그래머스 level2) - 에이젠

Lv. 2 점프와 순간 이동 - 성공

내풀이(1) : 테스트케이스 1번빼고 모두 통과, but 효율성 테스트에서 메모리 초과로 실패 

n이 10억 이상으로 가면서 배열 개수가 무지막지하게 늘어나기 때문이라고 추측.

재귀함수를 호출하는 방식으로 바꿔보자.

import java.util.*;
//일단 보자마자 풀이가 예상되지는 않는 문제...

public class Solution {
    public int solution(int n) {
        int ans = 0;

        int[] arr = new int[n+1]; //1~n까지의 칸.
        
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 2;
        for(int i = 4; i <= n ; i++){
            //홀수 -> 이전단계(짝수)비용 + 1
            if(i%2 == 1) arr[i] = arr[i-1] + 1;
            if(i%2 == 0) arr[i] = arr[i/2];
        }
        ans = arr[n];

        return ans;
    }
}

고친 풀이 : 재귀함수를 호출하는 방식으로 고침. 정확도 100%

public class Solution {
    public int solution(int n) {
       int ans = 0;
       ans = rec_func(n);
       return ans;
    }
   
    public int rec_func(int k){
       
        if(k == 1) return 1;
        if(k == 2) return 1;
        if(k == 3) return 2;
        if(k % 2 == 0) return rec_func(k/2);
        if(k % 2 == 1) return rec_func(k-1) +1;
        
        return 0;
    }
}

 

 

Lv. 2 3 x n 타일링 - 실패

참고한 풀이

 

https://zin0-0.tistory.com/31

프로그래머스 Lv.4) 3xn 타일링

 

 

Lv. 2 n^2 배열 자르기 - 실패 

각각 행과 열의 max값을 요소로 가진다는 점. 

class Solution {
    public  List<Long> solution(int n, long left, long right) {
        
        List<Long> list = new ArrayList<>();
        
        for(long i=left;i<right+1;i++){
             list.add(Math.max(i/n,i%n) + 1);
        }
        
        return list;
    }
}