[Java][Programmers] 할인 행사

프로그래머스

 

---

📌 접근 방식

처음에는 전체 상품을 구매할 수 있는 처음의 날이 언제인지 묻는 문제인 줄 알고 계속 그렇게 풀었는데, 알고보니 전체 상품을 구매할 수 있는 날이 총 며칠이냐고 물은거였음…… 하루쥉일 삽질했오요 ㅠ 계속 코드실행은 되는데 제출하면 12번만 맞았음.. 다들 참고하세요 🥲

---

⛔️ 처음 푼 코드

import java.util.*;
class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        List<String> list = new ArrayList<>();
        for(int i=0; i<number.length; i++) {
            for(int j=0; j<number[i]; j++) {
                list.add(want[i]);
            }
        }
        int size = list.size();
        if(size > discount.length) {
            return 0;
        }
        boolean flag = false;
        for(int i=0; i<=discount.length - size; i++) {
            List<String> tmp = new ArrayList<>(list);

            for(int j=i; j<size + i; j++) {
                String menu = discount[j];
                if(tmp.contains(menu)) {
                    tmp.remove(tmp.indexOf(menu));
                }
            }
            if(tmp.size()==0) {
                answer = i+1;
                flag = true;
                break;
            } 
        }
        
        if(flag)
            return answer;
        else return 0;
    }
}

⛔️ 현재 코드의 문제점

1. contains()와 remove()는 O(n) 연산이라, 최대 10만 개에 대해 반복할 경우 시간 초과 가능성이 높음.
2. List<String> list는 순서를 고려하지 않고 개수만 필요한 상황에 부적절한 자료구조임.
3. 문제는 정현이가 원하는 제품이 딱 그 수량만큼 10일 동안 할인 목록에 나와야 한다는 조건인데, 현재 코드는 그 조건을 정확하게 검증하지 못함.

---

PASS CODE

import java.util.*;

class Solution {
    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]);
        }

        for (int i = 0; i <= discount.length - 10; i++) {
            Map<String, Integer> windowMap = new HashMap<>();

            // 10일 간 할인 품목 수집
            for (int j = i; j < i + 10; j++) {
                windowMap.put(discount[j], windowMap.getOrDefault(discount[j], 0) + 1);
            }

            // wantMap과 windowMap 비교
            if (wantMap.equals(windowMap)) {
                answer++;
            }
        }

        return answer;
    }
}

➡️ getOrDefault()

• discount[j]가 windowMap에 이미 있다면 → 그 값을 가져오고 없다면 → 0을 기본값으로 사용하는 것!