[Level2] 더 맵게 답안 및 풀이

◇ 문제 설명

매운 것을 좋아하는 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 합니다.

 

◇ 입출력 예시

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

◇ 입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
     새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
     가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
    새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
    가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

◇ 초기 내용

※ [출처] 프로그래머스-코딩테스트 연습-문제명

※ 초기 내용을 참고하여 문제에 맞는 코드를 작성하세요.

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        return answer;
    }
}

 

---

◇ 풀이 과정

1. PriorityQueue(우선순위 큐)를 Integer형으로 선언하였다.
2. PriorityQueue에 scoville배열 각 요소의 값을 추가하였다.
3. PriorityQueue의 첫번째 값(가장 작은값)이 K보다 작다면
   
   • PriorityQueue의 값이 하나만 있는지 확인하고, 만약 하나뿐이라면 더이상 값을 K이상으로
     변환 시킬 수 없으므로 answer에 -1저장 후 break;
   • PriorityQueue의 값이 여러개라면 더 매운것을 만들어 저장해야하므로,
     PriorityQueue의 (첫번째값 + 두번째값 * 2)를 PriorityQueue에 저장후, 앞서 사용한 첫번째 값과 두번째 값을 PriorityQueue에서 삭제한다.
   • answer을 1증가한 후 3번의 조건이 일치한다면 계속해서 반복한다
4. answer의 값을 반환한다.

 

◇  참고 사항

첫번째, PriorityQueue

• 우선순위 큐를 구현한 객체이다.
• import java.util.PriorityQueue; 패키지를 작성해야 사용이 가능하다.
• 기본적으로 우선순위 큐에 값을 넣으면 오름차순으로 정렬이 된다(최소 힙 정렬이 구현된다)
  -> 오름차순으로 올라갈수록 우선순위가 낮아진다.
• Priority는 Heap으로 구성되어 있으며 이진트리 구조로 이루어져 있다.
• 시간복잡도로 O(log(n))의 시간이 걸린다.
• Heap과 Queue에 관한 자세한 설명은 이후 작성할 예정입니다.
• 주요 메서드
  

  메서드명	사용방법	설명
  add()	priorityQueue.add(value)	value값을 PriorityQueue에 저장합니다.
  poll()	priorityQueue.poll()	PriorityQueue의 첫번째값을 반환한 후 삭제합니다.
  remove()	priorityQueue.remove()	PriorityQueue의 첫번째 값을 제거합니다(null은 예외발생)
  peek()	priorityQueue.peek()	PriorityQueue의 첫번째 값은 반환합니다.
  clear()	priorityQueue.clear()	PriorityQueue의 모든 값을 삭제(초기화)합니다.

• PriorityQueue의 모든 요소에 접근할때(Iterator사용)
  
  • Iterator는 컬렉션에 저장되어 있는 요소들을 순회하며 읽어오는 것이다.
  • import java.util.Iterator을 작성해주어야한다.
  • 간단한 Iterator사용 방법
    • Iterator 객체를 만들어 준 후, 순회할 컬렉션과 연결해 준다.
      -> Iterator iter = priorityQueue.iterator();
    • 이후, 위에서 생성한 iter객체를 이용하여 각 요소에 접근한다.(while반복문 사용)
      -> while(iter.hasNext()){
              System.out.println(iter.next());
          }
• 우선순위 큐의 최소 힙 정렬을 사용하여 효율성과 편리성을 높였다.
  (ArrayList의 sort사용시, 시간이 오래걸려 효율성이 떨어지게 된다)
  
  ※ArrayList를 사용하여 구현한 코드 (아래 참조)

  import java.util.ArrayList;
  
  public static int solution(int[] scoville, int K) {
          int answer = 0;
          
          //scoville배열을 ArrayList로 저장
          ArrayList<Integer> scovilleList = new ArrayList<>();
          //ArrayList에 scoville배열의 값 저장
          for(int i = 0; i<scoville.length; i++){
              scovilleList.add(scoville[i]);
          }
          
          //scovilleList 리스트 내의 첫번째값(정렬된 첫번째값)이 K보다 작으면 실행
          while(scovilleList.get(0)<K){
              //ArrayList내 값이 하나밖에 없다면 더이상 값을 K이상으로
              //변환시킬 수 없으므로 answer에 -1저장 후 break
              if(scovilleList.size()==1){
                  answer = -1;
                  break;
              }
              //ArrayList를 정렬(우선순위 큐 사용시, 자동으로 정렬됨)
              Collections.sort(scovilleList);
              
              //더 매운 것을 만들어 저장
              scovilleList.add(scovilleList.get(0) + (scovilleList.get(1)*2));
              //매운걸 만든 재료 삭제
              scovilleList.remove(1);
              scovilleList.remove(0);
              answer++;
          }
          return answer;
      }

 

◇ 답안

import java.util.PriorityQueue;
//import java.util.Iterator;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        //PriorityQueue 변수 생성
        PriorityQueue<Integer> scovilleQueue = new PriorityQueue<>();
        //PriorityQueue에 scoville의 값 저장
        for(int i = 0; i<scoville.length; i++){
            scovilleQueue.add(scoville[i]);
        }
        
        /*
        //PriorityQueue의 모든 요소에 접근하여 출력하는 방법(iterator사용)
        Iterator iter = scovilleQueue.iterator();
        while(iter.hasNext()){
            System.out.println(iter.next());
        }
        */
        while(scovilleQueue.peek()<K){
            //PriorityQueue 값이 하나밖에 없다면 더이상 값을 K이상으로
            //변환시킬 수 없으므로 answer에 -1저장 후 break
            if(scovilleQueue.size()==1){
                answer = -1;
                break;
            }

            //더 매운 것을 만들어 저장
            //poll메서드를 이용하여 첫번째 값 반환 후 제거
            scovilleQueue.add(scovilleQueue.poll() + (scovilleQueue.poll()*2));
            answer++;
        }
        
        return answer;
    }
}

 

◇ 실행결과

더 맵게 실행결과

 

◇ 출처

https://programmers.co.kr/learn/challenges

코딩테스트 연습