프로그래머스 - 예산 java8

Sorbet·2021년 4월 25일
0

코테

목록 보기
24/35
  • 처음 풀이는 겉멋들어서 백트레킹으로 풀었는데 시간초과가 나버렸다.
  • 정확성은 맞다! 시간초과가 나서 정답이 맞는지 아닌지 모르지만 아무튼 정확성은 맞다구!!
public static void run(int dep,int remain,VO vo, int[] d,boolean[] used) {
        for(int i=0 ; i<d.length ; i++) {
            if(remain >= d[i] && used[i] == false) {
                vo.maxi = Math.max(dep,vo.maxi);
                used[i] = true; 
                run(dep+1,remain-d[i], vo,d,used);
                used[i] = false; 
            }
        }
    }
  • 그래서 그냥 정렬+for문 돌렸더니 맞았다.
  • 역시 나는 멋이랑 거리가 먼거같다. 코딩이나 착실하게 하고 살아야지
public static void run22(int dep,int remain,VO vo, int[] d,boolean[] used) {
        Arrays.sort(d);
        int sum=0;
        for(int i=0 ; i<d.length ; i++) {
            sum+= d[i];
            if(sum > remain) {
                vo.maxi = i;
                return;
            }
        }
        vo.maxi = d.length;
    }
  • 매서드를 넘나드는 전역변수가 하나 필요했는데 static으로 필드변수를 써도 되지만
  • 그냥 인트값 하나만 가지고있는 래핑클래스 만들어줬다. Integer클래스는 다풀고나서 생각났다..ㅋㅋ;
class VO {
    int maxi;
}
  • 엉망진창으로 풀면 나름의 매력이 있다. 언젠간 내가 다시 풀겠지?

전체코드

import java.util.*;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        boolean[] used = new boolean[d.length];
        VO v = new VO();
        //run(1,budget, v,d,used);
        run22(1,budget, v,d,used);
        return v.maxi;
    }

    public static void run(int dep,int remain,VO vo, int[] d,boolean[] used) {
        for(int i=0 ; i<d.length ; i++) {
            if(remain >= d[i] && used[i] == false) {
                vo.maxi = Math.max(dep,vo.maxi);
                used[i] = true; 
                run(dep+1,remain-d[i], vo,d,used);
                used[i] = false; 
            }
        }
    }

    public static void run22(int dep,int remain,VO vo, int[] d,boolean[] used) {
        Arrays.sort(d);
        int sum=0;
        for(int i=0 ; i<d.length ; i++) {
            sum+= d[i];
            if(sum > remain) {
                vo.maxi = i;
                return;
            }
        }
        vo.maxi = d.length;
    }

}
profile
Sorbet is good...!

0개의 댓글