🔥[99클럽 코테 스터디] 27일차 TIL - 할인 행사

⏳문제

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

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

정현이가 원하는 제품을 나타내는 문자열 배열 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
["banana", "apple", "rice", "pork", "pot"]	[3, 2, 2, 2, 1]	["chicken", "apple", "apple", "banana", "rice", "apple", "pork", "banana", "pork", "rice", "pot", "banana", "apple", "banana"]	3
["apple"]	[10]	["banana", "banana", "banana", "banana", "banana", "banana", "banana", "banana", "banana", "banana"]	0

📄입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다

입출력 예 #2

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

---

✏️풀이

discount의 맨 앞 요소부터 추출해 want에 포함되어 있는 지 확인하고, 만약 있다면 그 제품의 개수를 파악해 하나씩 차감해 나가면 될 것 같았다.
사고자 하는 제품을 모두 산 경우를 확인하기 위해 nowCount변수를 하나 생성해, 사야하는 물건의 총 개수로 초기화를 해 준 뒤, 원하는 물건을 하나씩 살 때마다 1씩 감소하도록 구현하였다.
그리고, 반복문의 끝에서 이 nowCount가 0인지를 확인해, 사고자 하는 제품을 모두 샀는 지에 대한 여부를 확인할 수 있었다.

단, 현재 할인 중인 제품이 want 배열에 포함되어 있는 지 확인하는 과정에서 for문을 사용하면 시간 복잡도가 커질 거 같아
정현이가 사고자 하는 제품과 개수를 key-value로 가지는 HashMap을 하나 만들기로 했다.

HashMap<String, Integer> wantMap = new HashMap<>();

그리고 나서, discount 배열을 순회해야 하는데
알뜰한 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치해야 한다 했으므로,
순회할 배열의 범위를 다음과 같이 지정해 주었다.

for (int i = 0; i <= discount.length - totalCount; i++)

여기서 totalCount는 필요한 제품의 총 개수인데, discount의 길이에서 이를 빼면, 연속 10일을 보장하는 범위 안에서 순회할 수 있다.
예를 들어, discount의 길이가 14이고, 원하는 제품이 10개라면,
discount의 4보다 큰 인덱스에서는 10일 연속으로 살 수 있는 경우의 수가 없다.

다음으로, HashMap에 사고자 하는 제품의 이름과 개수를 저장해 주었다.

for (int k = 0; k < want.length; k++) {
	wantMap.put(want[k], number[k]);
}  

이제, discount의 i번째 요소부터 10개의 요소에 방문하면서 현재 할인하는 제품이 wantMap에 있는 지 확인해 주어야 한다.
그래서 조건문을 두 개로 분기해 주었다.

• 현재 할인하는 제품이 wantMap에 존재하지 않거나, value값(해당 제품의 현재 필요한 개수)가 0이하인 경우
• 현재 할인하는 제품이 wantMap에 존재하고, value값(해당 제품의 현재 필요한 개수)가 1이상인 경우

for (int j = i; j < i + 10; j++) {
	if (wantMap.containsKey(discount[j]) == false || wantMap.get(discount[j]) <= 0) {
		break;
	}
	else {
		wantMap.put(discount[j], wantMap.get(discount[j]) - 1);
		nowCount--;
	}
}

첫 번째 조건의 경우에는 해당 제품을 구매할 필요가 없고, 10일 연속 구매가 절대 불가능하기 때문에,
반복문을 바로 빠져나오도록 해주었다.

두 번째 조건의 경우에는 해당 제품을 구매할 필요가 있는 경우이기 때문에, wantMap에서 해당 제품의 value값(필요한 개수)에 1을 빼주고, nowCount에도 1을 빼줌으로써, 해당 제품을 구매했다는 정보를 업데이트 해주었다.

마지막으로, nowCount가 0이면, 즉 사야 하는 제품을 모두 구매했다면, 최종 answer에 1을 더해줌으로써,
10일 연속으로 할인한 제품을 구매한 경우의 수를 증가시켜주었다.

if (nowCount == 0) {
	answer++;
}

---

👾최종 코드

import java.util.HashMap;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        int totalCount = 0;
        int nowCount = 0;
        HashMap<String, Integer> wantMap = new HashMap<>();

        // 필요한 물건의 총 개수
        for (int num : number) {
            totalCount += num;
        }
        

        for (int i = 0; i <= discount.length - totalCount; i++) {
            // hashMap 입력
            for (int k = 0; k < want.length; k++) {
                wantMap.put(want[k], number[k]);
            }  
            nowCount = 10;


            for (int j = i; j < i + 10; j++) {
                if (wantMap.containsKey(discount[j]) == false || wantMap.get(discount[j]) <= 0) {
                    break;
                }
                else {
                    wantMap.put(discount[j], wantMap.get(discount[j]) - 1);
                    nowCount--;
                }
            }
            if (nowCount == 0) {
                answer++;
            }
        }

        return answer;
    }
}

---

🔗문제 링크
💻Repository