[Algorithm] 5월 26일 알고리즘 연습

 

Lv. 1 예산 - 실패

https://programmers.co.kr/learn/courses/30/lessons/12982

코딩테스트 연습 - 예산

복습 내용 : 각 배열요소가 들어갈지 안들어갈지로 따지는 방법을 구상했지만 실패.

참고한 내용 : 배열을 정렬시킨다음에 사용 -> 작은 수부터 넣는 것이 최대한 효율

틀린 풀이 : 아래와 같이 하게되면 배열의 뒷부분에 있는 큰 예산을 포함시킬 수 없음.

import java.io.*;
import java.util.*;

class Solution {
    
    int possibleCount = 0;
    int bestCount = 0;
    
    //전체 예산
    int totalBudget = 0;
    int[] arrayCoop = {};
    boolean[] isSelected = {};
    
    public int solution(int[] d, int budget) {
        totalBudget = budget;
        arrayCoop  = d;
        isSelected = new boolean[d.length];
        rec_func(1, 0);
        int answer = bestCount;
        return bestCount;
    }
    
    //k번째 고를때 지금까지의 사용 예산
    public void rec_func(int k, int nowMoney){
        //M개 모두 골랐거나 예산 을 초과한다면
        if(k > arrayCoop.length || nowMoney > totalBudget){
            if(bestCount < possibleCount){
                bestCount = possibleCount;
                
            }
        }else{
            for(int cand = 0; cand < arrayCoop.length; cand++){
                if(isSelected[cand] == false){ //아직 고르지 않았을때만
                    possibleCount++;
                    isSelected[cand] = true;
                    //K번째
                    
                    rec_func(k+1, nowMoney + arrayCoop[cand]);
                    
                    possibleCount = 0 ;
                    isSelected[cand] = false;
                }
            }
        }
    }
}

 

 

 

Lv. 1 두 개 뽑아서 더하기 - 성공

복습할 내용 : 두개의 포인터?

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        
        int pointerI = 0;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        
        while(pointerI < numbers.length - 1){
            for(int i = pointerI + 1 ; i < numbers.length ; i++){
                int num = numbers[pointerI] + numbers[i];
                if(arr.contains(num) == false){
                    arr.add(num);
                }
            }
            pointerI++;
        }
        
        Collections.sort(arr);
        int[] result = new int[arr.size()];
        for(int i = 0; i < arr.size(); i++){
            result[i] = arr.get(i);
        }
        int[] answer = {};
        return result;
    }
}