[프로그래머스] 할인 행사

1. 문제

---

프로그래머스

2. 풀이 과정

---

회원이어야 할인을 받을 수 있고 할인은 가입시점부터 10일동안 유지된다.

1일에 회원에 가입한다면 1~10일까지의 할인상품이 정현이의 구매목록과 일치해야하고

2일에 회원에 가입한다면 2~11일까지의 할인 상품이 정현이의 구매목록과 일치해야한다. 

 

나는 이 문제를 해결하기 위해 매일매일 할인하는 상품과 일치하는 정현이의 상품의 남은 갯수를 하나 씩 지워주고 모든 상품의 남은 갯수가 0이 되면 그날의 9일 전이 올바른 회원가입날짜로 판단했다.

(10일에 모든상품을 구매한 경우 이는 1일의 회원가입 한 것이므로 9일 전)

그런 뒤 그런 날이 총 며칠인지 계산해줬다.

 

하지만 이 과정에서 몇가지 생각할 부분이 있다.

1. 상품의 남은 갯수를 어떻게 찾을 것인가?

상품은 want[] 배열에, 사야할 상품의 남은 갯수는 number[] 배열에 있다.

즉, 별도의 배열에 저장되어 있다는 말인데 이렇게 되면 매번 상품의 남은 갯수를 찾을 때마다 want[]배열을 뒤져 상품의 인인덱스를 찾아 낸 다음 number[]의 해당 인덱스 값을 수정해야 한다.

이는 매우 비효율적이다.

 

나는 이러한 문제를 해결하기 위해 해시 맵을 떠올렸다.

상품(want[])을 key로 남은 갯수(number[])를 value로 해서 해시맵에 저장한다면 상품명을 통해 남은 갯수를 빠르게 접근할 수 있게 된다.

 

2. 이전 할인상품을 제거해야한다.

2일에 회원가입해 2일~11일동안 상품할인을 받은 경우 1일의 할인 상품은 제외하고 계산해야 한다.

하지만 하루하루마다 해시맵에 할인상품을 반영했었기 때문에 2~11일인 경우에도 1일의 카운트가 반영되게 된다.

따라서 1일에 대한 할인 물건은 해시맵에서 다시 +1을 해줘야한다. 

 

 

예시를 한번 보도록하자

want: ["banana", "apple", "rice", "pork", "pot"]

number: [3, 2, 2, 2, 1]

discount: ["apple", "banana", "rice", "apple", "pork", "banana", "pork", "rice", "pot", "banana", "apple", "banana", "chicken", "apple"]인 경우이다.

 

1. 해시맵에 key: want[i], value: number[i]로 저장

 

2. discount의 원소를 하나씩 조회해 해시맵에 해당 상품의 갯수를 하나씩 줄인다.

• 사실 1~9일차(인덱스 상으론 0~8)까지의 과정은 크게 의미없는 과정이다. 왜냐하면 10일차는 돼야 1일차에 회원가입 했을 때 모든 상품 구매완료 여부를 판단할 수 있기 때문이다. 

3. 1일차에 회원가입 했을 경우(discount[9] 반영시)

• 모든 상품이 0이므로 1일차 회원가입시 모든 상품을 구매할 수 있다.
• 중간 정답: 1

4. 2일차에 회원가입 했을 경우(discount[10] 반영시)

• 2일차에 회원가입하는 경우 1일차의 할인상품은 구매하지 않는 것이다. 따라서 1일차 상품을 +1해야 한다.
• 이 경우엔 11일차 상품도 apple이었기 때문에 모든 상품이 0으로 유지된다.
• 중간 답: 2

5. 3일차에 회원가입 했을 경우 (discount[11] 반영시)

• 3일차에 회원가입하는 경우 2일차의 할인상품은 구매하지 않는 것이다. 따라서 2일차 상품을 +1해야 한다.
• 이 경우엔 12일차 상품도 banana이었기 때문에 모든 상품이 0으로 유지된다.
• 중간 답: 3

6. 4일차에 회원가입 했을 경우

• 4일차에 회원가입하는 경우 3일차의 할인상품은 구매하지 않는 것이다. 따라서 3일차 상품을 +1해야 한다. 
  따라서 rice에 +1을 해줬다.
• 13일차 상품은 chicken인데 chicken은 구매 상품 목록에 없으므로 그대로 유지된다.
• 이 경우 모든 상품이 0이 아니므로 3일차에 회원가입하면 안된다.

7. 5일차에 회원가입 했을 경우

• 5일차에 회원가입하는 경우 4일차의 할인상품은 구매하지 않는 것이다. 따라서 4일차 상품을 +1해야 한다. 
• 이 경우 14일차 상품도 apple이었기 때문에 apple은 그대로 0으로 유지된다.
• 이 경우 모든 상품이 0이 아니므로 5일차에 회원가입하면 안된다.

최종답: 3

 

3. 내 코드

---

import java.util.*;
class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
    
        HashMap<String, Integer> map = new HashMap<>();
        int day_count = 0;
        
        for(int i = 0; i < want.length; i++) {
            map.put(want[i], number[i]);
        }
        
        
        // 매일 할인하는 상품 내 구매목록에서 지워주기
        for(int i = 0; i < discount.length; i++) {
            
            // 매일 회원을 가입한다고 했을 때, 가입하고 10일이 지나면 10일 전에 할인받았던
            // 상품은 할인을 받지 못함 따라서 그 상품이 내가 사려는 상품이라면  
            // 다시 +1을 해줘야 함
            int product_left;
            if(i >= 10 && map.containsKey(discount[i - 10])) { 
                product_left = map.get(discount[i - 10]);
                map.put(discount[i - 10], ++product_left); // 해당 상품 +1
            }

            // 해당 날짜의 할인하는 상품이 내가 사려고 하는 물품이라면
            if(map.containsKey(discount[i])) { 
        
                // 해당 상품 -1 해주기
                product_left = map.get(discount[i]);
                map.put(discount[i], --product_left); 
                
            }
            
            // 만약 map의 모든 value가 0이라면 쇼핑 끝
            boolean isFinish = true;
            List<Integer> list = new ArrayList<>();
            for(String product: map.keySet()) {
                list.add(map.get(product));
            }
        
            
            for(String product: map.keySet()) {
                if(map.get(product) > 0) {
                    isFinish = false;
                    break;
                }
            }
            
            if(isFinish) day_count++;
            else isFinish = true;
        }
        
        return day_count;
        
    }
}

시간 복잡도

• O(N)

 

4. 피드백

---

• 두 개의 배열이 있고 배열들이 서로 연관된 관계라면 하나를 key 다른 하나를 value로 지정해 해시맵을 사용하면 좋다.
  배열을 통해 다른 배열의 값을 참조하려면 O(N)이 걸리지만 key 값을 통해 value를 찾으면 O(1)이 걸리기 때문이다.