[프로그래머스] Level2 _42626번: 더 맵게 (JAVA)

문제 42626번

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

코딩테스트 연습 - 더 맵게

 

 

 

 

 

풀이 (실패 : 시간초과)

List 사용 풀이 (테스트 케이스 통과, 효율성 시간초과 발생)

package seohae.algorithm.level2;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * https://programmers.co.kr/learn/courses/30/lessons/42626
 */

public class Lesson_048_42626_시간초과 {
    public static void main(String[] args) {
        Lesson_048_42626_시간초과 lesson = new Lesson_048_42626_시간초과();

        int[] a = new int[]{1,2,3};
        System.out.println(lesson.solution(a, 11));
    }

    public int solution(int[] scoville, int K) {
        int answer = 0;

        /* Array to List */
        List<Integer> intList = Arrays.stream(scoville).boxed().collect(Collectors.toList());

        while(true) {
            /* 정렬 */
            Collections.sort(intList);

            /* 원소가 1개일 경우 */
            if (intList.size() == 1) {
                if (intList.get(0) >= K) { /* K보다 크거나 같다면 answer 리턴 */
                    return answer;
                } else { /* 그 외는 스코빌 지수를 K 이상으로 만들 수 없음으로 판단 */
                    return -1;
                }
            }

            /* 스코빌 지수 만족 */
            if (intList.get(0) >= K) {
                return answer;
            } else {
                int target = intList.get(0); /* 가장 작은 수 */
                int second = intList.get(1); /* 두번째로 작은 수 */

                int result = target + (second * 2);

                intList.remove(0); /* 가장 작은수 제거 */
                intList.remove(0); /* 가장 작은수 제거 후 0번째는 두번째로 작은 수 제거 */
                intList.add(result);

                answer++;
            }
        }

    }
}

 

 

 

 

 

 

풀이 (완료)

PriorityQueue 우선순위큐 사용

package seohae.algorithm.level2;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
 * https://programmers.co.kr/learn/courses/30/lessons/42626
 */

public class Lesson_048_42626_우선순위큐 {
    public static void main(String[] args) {
        Lesson_048_42626_우선순위큐 lesson = new Lesson_048_42626_우선순위큐();

        int[] a = new int[]{1,2,3};
        System.out.println(lesson.solution(a, 11));
    }

    public int solution(int[] scoville, int K) {
        int answer = 0;

        // PriorityQueue를 사용해서 숫자가 작을수록 우선순위를 가지게 저장
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        for (int pri : scoville) {
            pq.offer(pri);
        }

        while(!pq.isEmpty()) {
            /* 원소가 1개일 경우 */
            if (pq.size() == 1) {
                if (pq.peek() >= K) { /* K보다 크거나 같다면 answer 리턴 */
                    return answer;
                } else { /* 그 외는 스코빌 지수를 K 이상으로 만들 수 없음으로 판단 */
                    return -1;
                }
            }

            /* 스코빌 지수 만족 */
            if (pq.peek() >= K) {
                return answer;
            } else {
                int target = pq.poll(); /* 가장 작은 수 */
                int second = pq.poll(); /* 두번째로 작은 수 */

                int result = target + (second * 2);

                pq.offer(result);

                answer++;
            }
        }

        return answer;
    }
}