- [프로그래머스 / JAVA] Level 2 메뉴 리뉴얼 (72411)
- [프로그래머스 / JAVA] Level 2 행렬 테두리 회전하기 (77485)
- [프로그래머스 / JAVA] Level 2 짝지어 제거하기 (12973)
- [프로그래머스 / MySQL] Level 2 루시와 엘라 찾기 (59046)
- [프로그래머스 / MySQL] Level 2 고양이와 개는 몇 마리 있을까 (59040)
- [프로그래머스 / JAVA] Level 2 타겟 넘버 (43165)
👀 [프로그래머스 / JAVA] Level 2 더 맵게 (42626)
- [프로그래머스 / JAVA] Level 2 기능개발 (42586)
- [프로그래머스 / JAVA] Level 2 124 나라의 숫자 (12899)
- [프로그래머스 / JAVA] Level 2 멀쩡한 사각형 (62048)
- [프로그래머스 / JAVA] Level 2 단체사진 찍기 (1835)
- [프로그래머스 / JAVA] Level 2 카카오프렌즈 컬러링북 (1829)
- [프로그래머스 / JAVA] Level 2 오픈채팅방 (42888)
- [프로그래머스 / JAVA] Level 2 문자열 압축 (60057)
- [프로그래머스 / JAVA] Level 1 직사각형 별찍기 (12954)
- [프로그래머스 / JAVA] Level 1 x만큼 간격이 있는 n개의 숫자 (12954)
- [프로그래머스 / JAVA] Level 1 행렬의 덧셈 (12950)
- [프로그래머스 / JAVA] Level 1 핸드폰 번호 가리기 (12948)
- [프로그래머스 / JAVA] Level 1 하샤드 수 (12947)
- [프로그래머스 / JAVA] Level 1 평균 구하기 (12944)
- [프로그래머스 / JAVA] Level 1 콜라츠 추측 (12943)
- [프로그래머스 / JAVA] Level 1 최대공약수와 최소공배수 (12940)
- [프로그래머스 / JAVA] Level 1 짝수와 홀수 (12937)
- [프로그래머스 / JAVA] Level 1 제일 작은 수 제거하기 (12935)
- [프로그래머스 / JAVA] Level 1 정수 제곱근 판별 (12934)
- [프로그래머스 / JAVA] Level 1 정수 내림차순으로 배치하기 (12933)
- [프로그래머스 / JAVA] Level 1 자연수 뒤집어 배열로 만들기 (12932)
- [프로그래머스 / JAVA] Level 1 자릿수 더하기 (12931)
- [프로그래머스 / JAVA] Level 1 이상한 문자 만들기 (12930)
- [프로그래머스 / JAVA] Level 1 약수의 합 (12928)
- [프로그래머스 / JAVA] Level 1 시저 암호 (12926)
- [프로그래머스 / JAVA] Level 1 문자열을 정수로 바꾸기 (12925)
- [프로그래머스 / JAVA] Level 1 수박수박수박수박수박수? (12922)
- [프로그래머스 / JAVA] Level 1 소수 찾기 (12921)
- [프로그래머스 / JAVA] Level 1 서울에서 김서방 찾기 (12919)
- [프로그래머스 / JAVA] Level 1 문자열 다루기 기본 (12918)
- [프로그래머스 / JAVA] Level 1 문자열 내림차순으로 배치하기 (12917)
- [프로그래머스 / JAVA] Level 1 문자열 내 p와 y의 개수 (12916)
- [프로그래머스 / JAVA] Level 1 문자열 내 마음대로 정렬하기 (12915)
- [프로그래머스 / JAVA] Level 1 두 정수 사이의 합 (12912)
- [프로그래머스 / JAVA] Level 1 나누어 떨어지는 숫자 배열 (12910)
- [프로그래머스 / JAVA] Level 1 같은 숫자는 싫어 (12906)
- [프로그래머스 / MySQL] Level 1 상위 n개 레코드 (59405)
- [프로그래머스 / JAVA] Level 1 다트 게임 (17682)
- [프로그래머스 / MySQL] Level 1 여러 기준으로 정렬하기 (59404)
- [프로그래머스 / JAVA] Level 1 가운데 글자 가져오기 (12903)
- [프로그래머스 / JAVA] Level 1 비밀지도 (17681)
- [프로그래머스 / JAVA] Level 1 부족한 금액 계산하기 (82612)
- [프로그래머스 / MySQL] Level 1 동물의 아이디와 이름 (59403)
- [프로그래머스 / JAVA] Level 1 나머지가 1이 되는 수 찾기 (87389)
- [프로그래머스 / JAVA] Level 1 최소직사각형 (86491)
- [프로그래머스 / MySQL] Level 1 어린 동물 찾기 (59037)
- [프로그래머스 / JAVA] Level 1 2016년 (12901)
- [프로그래머스 / MySQL] Level 1 아픈 동물 찾기 (59036)
- [프로그래머스 / JAVA] Level 1 두 개 뽑아서 더하기 (68644)
- [프로그래머스 / MySQL] Level 1 이름이 있는 동물의 아이디 (59407)
- [프로그래머스 / JAVA] Level 1 두 개 뽑아서 더하기 (12982)
- [프로그래머스 / JAVA] Level 1 예산 (12982)
- [프로그래머스 / JAVA] Level 1 3진법 뒤집기 (68935)
- [프로그래머스 / JAVA] Level 1 약수의 개수와 덧셈 (77884)
- [프로그래머스 / JAVA] Level 1 실패율 (42889)
- [프로그래머스 / JAVA] Level 1 폰켓몬 (1845)
- [프로그래머스 / MySQL] Level 1 이름이 없는 동물의 아이디 (59039)
- [프로그래머스 / MySQL] Level 1 최댓값 구하기 (59415)
- [프로그래머스 / MySQL] Level 1 모든 레코드 조회하기 (59034)
- [프로그래머스 / JAVA] Level 1 체육복 (42862)
- [프로그래머스 / JAVA] Level 1 모의고사 (42840)
- [프로그래머스 / JAVA] Level 1 완주하지 못한 선수 (42576)
- [프로그래머스 / JAVA] Level 1 소수 만들기 (12977)
- [프로그래머스 / JAVA] Level 1 음양 더하기 (76501)
- [프로그래머스 / JAVA] Level 1 K번째수 (42748)
- [프로그래머스 / JAVA] Level 1 내적 (70128)
- [프로그래머스 / JAVA] Level 1 없는 숫자 더하기 (86051)
- [프로그래머스 / JAVA] Level 1 크레인 인형뽑기 게임 (64061)
- [프로그래머스 / JAVA] Level 1 키패드 누르기 (67256)
- [프로그래머스 / JAVA] Level 1 숫자 문자열과 영단어 (81301)
- [프로그래머스 / JAVA] Level 1 신규 아이디 추천 (72410)
- [프로그래머스 / JAVA] Level 1 로또의 최고 순위와 최저 순위 (77484)
더 맵게 🔗
🔗 더 맵게
문제 설명 🔗
매운 것을 좋아하는 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인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]
모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.
풀이 🔗
문제 자체는 간단하다. scoville
중 가장 작은 값과 두 번째로 작은 값을 호출하여 섞는다. 이 과정을 수행하여 모든 요소의 값이 K
이상이 될 때까지 반복한다.
만약, 모든 연산을 수행했음에도 K
이상이 되지 못 하는 음식이 있을 경우 -1을 반환한다.
뽑아야 하는 요소의 법칙이 정해져 있으므로 조합은 맞지 않다.
- 데이터를 호출할 때마다 가장 작은 값이 나와야 한다.
- 데이터의 삽입, 삭제가 자유롭다.
얼핏 보면 ArrayList
사용해서 정렬하면 되지 않을까? 싶지만 이 방법은 효율성이 극히 떨어진다. 연산을 수행할 때마다 ArrayList
의 정렬 과정이 필요하기 때문.
이 문제는 PriorityQueue
객체를 알고 있다면 쉽게 풀 수 있고, 아니라면 고생 좀 하게 되는 문제다.
PriorityQueue
는 이름 그대로 큐지만, 일반적인 LIFO 방식이 아니다. PriorityQueue
의 독특한 규칙은 아래와 같다.
- 데이터의 우선순위를 파악하여 가장 높은 우선순위의 데이터를 먼저 출력
- 이진트리 방식을 사용하으로 시간복잡도는
- 베이스는
Queue
를 따른다.
PriorityQueue
의 특징은 이 문제와 매우 적합하다. 각 요소가 숫자로 이루어져 있으므로, 가장 낮은 숫자를 우선순위로 지정하여 데이터를 출력하면, 굳이 정렬을 사용하지 않고도 가장 작은 데이터를 호출할 수 있을 것이다.
JAVA
0 | // 우선순위가 낮은 순 |
1 | PriorityQueue<Integer> queue = new PriorityQueue<>(); |
2 | |
3 | // 우선순위가 높은 순 |
4 | PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder()); |
PriorityQueue
를 선언할 때, 우선순위를 지정할 수 있다.
이 문제는 가장 작은 수를 최우선으로 뽑아야 하므로, 우선순위가 낮은 순으로 뽑는 것이 적절할 것이다.
PriorityQueue
에서 뽑은 요소가 K
를 넘지 않을 경우, 아직 덜 매운 음식이 있으므로 연산을 수행한다.
K
를 넘는다면, 가장 안 매운 음식도 K
를 넘으므로 연산을 수행할 필요가 없다.
코드 🔗
JAVA
0 | import java.util.Objects; |
1 | import java.util.PriorityQueue; |
2 | |
3 | /** |
4 | * 더 맵게 클래스 |
5 | * |
6 | * @author RWB |
7 | * @since 2021.12.27 Mon 13:43:34 |
8 | */ |
9 | class Solution |
10 | { |
11 | /** |
12 | * 해답 반환 메서드 |
13 | * |
14 | * @param scoville: [int[]] 음식의 스코빌 지수 배열 |
15 | * @param K: [int] 목표 스코빌 지수 |
16 | * |
17 | * @return [int] 해답 |
18 | */ |
19 | public int solution(int[] scoville, int K) |
20 | { |
21 | int answer; |
22 | |
23 | // 섞을 요소가 부족할 경우 |
24 | if (scoville.length < 2) |
25 | { |
26 | answer = -1; |
27 | } |
28 | |
29 | // 섞을 요소가 충분할 경우 |
30 | else |
31 | { |
32 | PriorityQueue<Integer> queue = new PriorityQueue<>(); |
33 | |
34 | answer = 0; |
35 | |
36 | for (int item : scoville) |
37 | { |
38 | queue.add(item); |
39 | } |
40 | |
41 | while (Objects.requireNonNull(queue.peek()) < K) |
42 | { |
43 | // 섞을 요소가 부족할 경우 |
44 | if (queue.size() < 2) |
45 | { |
46 | answer = -1; |
47 | |
48 | break; |
49 | } |
50 | |
51 | queue.add(Objects.requireNonNull(queue.poll()) + (Objects.requireNonNull(queue.poll()) * 2)); |
52 | |
53 | answer++; |
54 | } |
55 | } |
56 | |
57 | return answer; |
58 | } |
59 | } |
queue.poll()
, queue.peek()
이 null
을 반환할 가능성이 있으므로, Objects.requireNonNull()
를 사용하여 관련 오류를 제거한다.
Objects.requireNonNull()
가 없어도 동작에 영향은 없다.
📆 작성일
2021-12-28 Tue 03:15:05
📚 카테고리
🏷️ 태그