[알고리즘 문제] 과자 많이 먹기 (Programmers)

과자 많이 먹기

 프로그래머스로 문제 풀러 가기 

[문제]

과자를 좋아하는 동우는 책상 위에 일렬로 놓아진 과자를 발견하였습니다. 과자에는 맛을 숫자로 평가한 종이가 붙어 있습니다. 동우는 맨 왼쪽부터 순서대로 과자를 먹기로 하였습니다. 동우는 먹을 과자를 고를 때 이전에 먹은 과자보다 맛이 더 좋은 과자만 먹습니다.

제일 처음에 맛이 3인 과자를 먹었다면, 다음에는 4보다 작은 맛의 과자는 먹지 않습니다.

책상위에 놓인 과자의 맛이 입력되면, 동우가 최대 과자를 몇 개를 먹을 수 있는지 반환해주는 eatCookie 함수를 완성하세요.

예를 들어 [1, 4, 2, 6, 3, 4, 1, 5] 가 입력된다면 동우는 1, 3, 5, 6, 8번째 과자(각각의 맛은 1, 2, 3, 4, 5)를 골라 총 5개를 먹을 수 있고, 5개보다 더 많이 먹을 수 있는 방법은 없으므로 5를 리턴하면 됩니다.

[나의 답안]

class EatCookie
{
    public int eatCookie(int []cookies) {
        int cnt[] = new int[cookies.length];
    
        //각각 과자마다 그 과자를 먹기까지 그 전에 먹고 올 수 있는 최대의 갯수를 구하기
        for(int i=0; i<cookies.length; i++) {      
          cnt[i] = getCntByPre(cnt, i, cookies);
        }
    
        return getMaxInArr(cnt);
    }
  
    //현재보다 맛없는 것들 중 이전까지의 최대 먹은횟수 +1 반환하는 메소드
    public int getCntByPre(int[] cnt, int idx, int[] cookies) {
        int max = 0;
    
        if(idx == 0) return 1;
    
        for(int i=0;i<idx;i++) {
              if(cnt[i] > max && cookies[i] < cookies[idx])
            max = cnt[i];
        }
        
        return max+1;
    }
  
    //배열의 최대값 구하는 메소드
    public int getMaxInArr(int[] arr) {
        int max = 0;
        for(int i=0;i<arr.length;i++) {
            if(arr[i] > max)
                max = arr[i];
        }
 
        return max;
    }
 
    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        EatCookie e = new EatCookie();
        int []cookies = {1, 4, 2, 6, 3, 4, 1, 5};
        System.out.println(e.eatCookie(cookies));
    }
}