알고리즘/프로그래머스

[JAVA] 프로그래머스 Lv2.더 맵게

수진보배 2020. 11. 5. 16:30
728x90

<문제>

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

<제한 사항>

  • scoville의 길이는 2 이상 1,000,000 이하입니다.
  • K는 0 이상 1,000,000,000 이하입니다.
  • scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

<풀이>

 

* 처음 문제를 봤을 때 arraylist를 이용해 구현했으나 효율성 테스트에서 실패 *

 

public class test3 {

    public static void main(String[] args) {

        int[] scoville = {1,2,3,9,10,12};
        int K=7;
        int answer = 0;

 

        ArrayList<Integer> list = new ArrayList<Integer>();     //arraylist에 스코빌 배열을 추가한다.

        for(int i=0; i<scoville.length; i++) {

            list.add(scoville[i]);

        }

        Collections.sort(list);                                  // list를 정렬해서 작은 수를 찾을 수 있게 한다.

 

        while(list.get(0)<K) {                 

           if( list.size()==1){                                 // list의 크기가 1이면 스코빌지수를 섞을 수 없으므로 -1을 반환.

                answer = -1;
                break;  
            }

            int num = list.get(0)+(list.get(1)*2);         // 가장 작은 두 수로 스코빌 지수를 구하고 두 수 삭제.

                                                                     // 구한 스코빌 지수를 다시 list에 추가.

            list.remove(1);

            list.remove(0);

            list.add(num);

            answer++;                                          // 섞은 횟수를 추가 해줌

 

            Collections.sort(list);                         

        }

        System.out.println(answer);

    }

}  

 

728x90