Part of your World

문제 설명

매운 것을 좋아하는 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. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
3. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.가진 음식의 스코빌 지수 = [13, 9, 10, 12]
4. 새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13

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

package LV2;

import java.util.PriorityQueue;

public class H42626 {
    public int solution(int[] scoville, int K) {
        // 횟수를 세기 위한 변수 초기화
        int answer = 0;

        // 우선순위 큐 (최소 힙) 초기화
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // 모든 스코빌 지수를 힙에 삽입
        for (int aScoville : scoville) {
            heap.offer(aScoville);
        }

        // 힙의 최솟값이 K 미만인 동안 반복
        while (heap.peek() < K) {
            // 힙의 크기가 2 미만이면 K 이상으로 만들 수 없으므로 -1 반환
            if (heap.size() < 2) return -1;

            // 스코빌 지수가 가장 낮은 음식과 그 다음으로 낮은 음식을 가져옴
            int first = heap.poll();
            int second = heap.poll();

            // 새로운 음식의 스코빌 지수 계산
            int newScoville = first + (second * 2);

            // 새로운 음식을 힙에 삽입
            heap.offer(newScoville);

            // 섞은 횟수 증가
            answer++;
        }

        // 모든 음식의 스코빌 지수를 K 이상으로 만드는데 필요한 최소 섞기 횟수 반환
        return answer;
    }
}

최소 힙(Minimum Heap) 자료구조를 사용하여 풀 수 있다. 최소 힙을 사용하면 스코빌 지수가 가장 낮은 음식을 효율적으로 찾을 수 있기 때문이다.

PriorityQueue를 통해 최소 힙을 구성하고, 주어진 scoville 배열의 각 원소를 힙에 추가한다. 그리고 힙의 최소값(즉, 스코빌 지수가 가장 낮은 음식)이 K 이상이 될 때까지 두 가장 낮은 스코빌 지수의 음식을 섞는다. 섞을 때마다 answer를 1씩 증가시키고, 섞은 후의 새로운 음식을 다시 힙에 추가한다. 만약 힙에 원소가 2개 미만으로 남아 있고 최소 스코빌 지수가 여전히 K 미만이라면 모든 음식의 스코빌 지수를 K 이상으로 만드는 것이 불가능하다는 의미이므로 -1을 반환한다.

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

• 1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers target return

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4 +4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

package LV2;

public class H43165 {
    // 주요 함수: 주어진 배열과 목표값을 입력으로 받아서 조합의 수를 리턴함
    public int solution(int[] numbers, int target) {
        // 깊이 우선 탐색(dfs) 함수를 호출하여 조합의 수를 계산하고 반환
        // 초기 인덱스는 0이고, 초기 합계는 0
        return dfs(numbers, target, 0, 0);
    }

    // 깊이 우선 탐색 (dfs) 함수 정의
    // 인풋으로 숫자 배열, 목표값, 현재 인덱스, 현재 합계를 받음
    public int dfs(int[] numbers, int target, int index, int sum) {
        // 모든 숫자를 검사했을 때(인덱스가 숫자 배열의 길이와 같을 때)
        if(index == numbers.length) {
            // 현재 합계와 목표값이 같다면, 조합의 수는 1
            if(sum == target) {
                return 1;
            }
            // 그렇지 않다면, 조합의 수는 0
            return 0;
        }

        // dfs 함수를 재귀적으로 두 번 호출하여 각 숫자에 대해 더하거나 빼는 경우를 모두 탐색
        // 이후에 이 두 가지 경우에서 나온 조합의 수를 모두 더함
        return dfs(numbers, target, index + 1, sum + numbers[index]) // 현재 숫자를 더하는 경우
                + dfs(numbers, target, index + 1, sum - numbers[index]); // 현재 숫자를 빼는 경우
    }
}

주어진 숫자들을 더하거나 빼서 주어진 타겟 넘버를 만드는 방법의 수를 찾는 것이다.

이 문제를 해결하기 위해 재귀함수를 사용할 수 있다. 각 숫자에 대해 재귀함수를 두 번 호출하면서 한 번은 해당 숫자를 더하고, 한 번은 뺀다. 이렇게 하면 모든 가능한 조합을 탐색할 수 있다. 마지막 숫자까지 계산했을 때 결과가 타겟 넘버와 같다면 카운트를 1 증가시킨다.

dfs 함수는 재귀를 사용하여 문제를 해결한다. index 파라미터는 현재 숫자의 위치를 나타내며, **sum**은 현재까지의 합계를 나타낸다. dfs 함수는 두 가지 경우를 재귀적으로 탐색하며, 하나는 현재 숫자를 더하는 경우, 다른 하나는 빼는 경우이다. 이렇게 모든 가능한 경우를 탐색하면서 타겟 넘버를 만드는 경우의 수를 찾는다.

문제 설명

XYZ 마트는 일정한 금액을 지불하면 10일 동안 회원 자격을 부여합니다. XYZ 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 합니다. 할인하는 제품은 하루에 하나씩만 구매할 수 있습니다. 알뜰한 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 합니다.

예를 들어, 정현이가 원하는 제품이 바나나 3개, 사과 2개, 쌀 2개, 돼지고기 2개, 냄비 1개이며, XYZ 마트에서 15일간 회원을 대상으로 할인하는 제품이 날짜 순서대로 치킨, 사과, 사과, 바나나, 쌀, 사과, 돼지고기, 바나나, 돼지고기, 쌀, 냄비, 바나나, 사과, 바나나인 경우에 대해 알아봅시다. 첫째 날부터 열흘 간에는 냄비가 할인하지 않기 때문에 첫째 날에는 회원가입을 하지 않습니다. 둘째 날부터 열흘 간에는 바나나를 원하는 만큼 할인구매할 수 없기 때문에 둘째 날에도 회원가입을 하지 않습니다. 셋째 날, 넷째 날, 다섯째 날부터 각각 열흘은 원하는 제품과 수량이 일치하기 때문에 셋 중 하루에 회원가입을 하려 합니다.

정현이가 원하는 제품을 나타내는 문자열 배열 want와 정현이가 원하는 제품의 수량을 나타내는 정수 배열 number, XYZ 마트에서 할인하는 제품을 나타내는 문자열 배열 discount가 주어졌을 때, 회원등록시 정현이가 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 return 하는 solution 함수를 완성하시오. 가능한 날이 없으면 0을 return 합니다.

제한사항

• 1 ≤ want의 길이 = number의 길이 ≤ 10
  • 1 ≤ number의 원소 ≤ 10
  • number[i]는 want[i]의 수량을 의미하며, number의 원소의 합은 10입니다.
• 10 ≤ discount의 길이 ≤ 100,000
• want와 discount의 원소들은 알파벳 소문자로 이루어진 문자열입니다.
  • 1 ≤ want의 원소의 길이, discount의 원소의 길이 ≤ 12

입출력 예

want number discount result

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 사과가 할인하는 날이 없으므로 0을 return 합니다.

package LV2;

import java.util.HashMap;
import java.util.Map;

public class H131127 {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;

        // 정현이가 원하는 제품들과 그 수량을 맵에 저장
        Map<String, Integer> wantMap = new HashMap<>();
        for (int i = 0; i < want.length; i++) {
            wantMap.put(want[i], number[i]);
        }

        // 할인 제품 목록을 10일 동안의 윈도우로 슬라이드하면서 
        // 해당 기간 동안의 제품과 수량을 또 다른 맵에 저장
        for (int i = 0; i <= discount.length - 10; i++) {
            Map<String, Integer> discountMap = new HashMap<>();
            for (int j = i; j < i + 10; j++) {
                discountMap.put(discount[j], discountMap.getOrDefault(discount[j], 0) + 1);
            }

            // 두 맵을 비교하여 원하는 제품의 수량을 모두 충족시키는지 확인
            boolean isMatch = true;
            for (String key : wantMap.keySet()) {
                if (wantMap.get(key) > discountMap.getOrDefault(key, 0)) {
                    isMatch = false;
                    break;
                }
            }

            // 만약 원하는 제품의 수량을 모두 충족시킨다면, 정답을 1 증가시킨다.
            if (isMatch) {
                answer++;
            }
        }

        // 계산된 정답을 반환
        return answer;
    }
}

"슬라이딩 윈도우" 기법을 사용하여 10일동안 할인하는 제품이 정현이의 원하는 제품 목록과 일치하는지 확인하기 그리고 그 기간 동안 원하는 제품의 수량을 모두 충족시키는지를 확인

정현이가 원하는 제품과 그 수량을 맵으로 만든다. 그런 다음 할인 제품 목록을 10일 동안의 윈도우로 슬라이드하면서 해당 기간 동안의 제품과 수량을 또 다른 맵으로 만든다. 그리고 이 두 맵을 비교하여 원하는 제품의 수량을 모두 충족시키는지 확인한다. 만약 충족시킨다면 정답을 1 증가시킵니다. 이 작업을 할인 제품 목록이 끝날 때까지 반복