탐욕(그리디) 알고리즘

쉬운 문제라서 한 번에 맞혔다. 근데 그리디로 푼 건지 모르겠어서 더 좋은 방법이 있나 찾아보는 중

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] student = new int[n];
        
        for(int i : lost){
            student[i-1] -=1;
        }
        
        for(int i : reserve){
            student[i-1] +=1;
        }
        
        for(int i=0; i<student.length; i++){
            if(student[i]==-1){
                if(i!=0){
                    if(student[i-1] == 1){
                        student[i]+=1;
                        student[i-1]-=1;
                    }
                }
                if(i!=student.length-1){
                    if(student[i+1] == 1){
                        student[i]+=1;
                        student[i+1]-=1;
                    }
                }
            }
        }
        
        int count = 0;
       for(int i : student){
           if(i!=-1){
               count++;
           }
       }
        

        return count;
    }
}

programmers.co.kr/learn/courses/30/lessons/42862#qna

코딩테스트 연습 - 체육복

 

탐욕 알고리즘이 필요할 때

: 부분적으로 최적인 해가 전체적으로 최적이 아닌 해가 존재하지 않을 때

: 즉, 현재 상황에서 가장 좋은 결정을 하면 문제가 풀릴 때!