[programmers] 할인 행사

할인 행사 문제

문제 설명

마트에서 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 한다. 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 한다.

문제 풀이 1.

먼저, 원하는 상품과 수량을 담을 map과 discount 배열을 돌면서 넣어줄 map을 선언해 주었다. 그다음 while문을 돌면서 10개씩 제품을 map에 담아 비교해주고 동일하다면 answer를 1 증가시켜 주었다.

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

    Map<String, Integer> map = new HashMap<>();
    Map<String, Integer> basket = new HashMap<>();
    for (int i = 0; i < want.length; i++) {
        map.put(want[i], number[i]);
        basket.put(want[i], 0);
    }

    int index = 0;
    int nowIndex = 0;
    int len = 0;
    while (true) {
        // 원하는 제품이 모두 들어있다면 answer 1증가시킴
        if (basket.equals(map)) {
            answer++;
        }

        if (nowIndex == discount.length) {
            break;
        }

        // 10일 동안의 제품을 모두 확인했으면 이전 index의 제품은 지워준다.
        if (len == 10) {
            basket.put(discount[index], basket.get(discount[index]) - 1);
            index++;
            len -= 1;
            continue;
        }

        // 현재 인덱스에서 원하는 제품이 아니면 다음 인덱스로 넘어감
        if (!map.containsKey(discount[index])) {
            index++;
            nowIndex++;
            continue;
        }

        // 현재 인덱스부터 10일동안의 할인 제품 목록을 확인한다.
        if (map.containsKey(discount[nowIndex])) {
            basket.put(discount[nowIndex], basket.get(discount[nowIndex]) + 1);
            nowIndex++;
            len++;
        }
    }

    return answer;
}

풀이 1 실행결과

코드 실행은 통과 하였는데, 정확성 채점하기에서 시간초과가 났다. 구현이 잘못되었다 판단되어 풀이 2번처럼 for문으로 코드를 다시 작성하였다.

문제풀이 2.

풀이 1과 map에 원하는 상품과 수량을 넣는 과정은 동일하고 할인하는 요일에 포함이 되어있는지 확인하는 과정만 수정해 보았다.
10일씩 세일 상품들을 확인하면서 map에 넣어주고 원하는 제품과 수량을 담아뒀던 map과 비교하여 동일하다면 answer를 1증가 시켜 주었다.

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

    Map<String, Integer> map = new HashMap<>();
    for (int i = 0; i < want.length; i++) {
        map.put(want[i], number[i]);
    }

    for (int i = 0; i <= discount.length - 10; i++) {
        Map<String, Integer> basket = new HashMap<>();
        for (int j = 0; j < 10; j++) {
            String item = discount[i + j];
            basket.put(item, basket.getOrDefault(item, 0) + 1);
        }
        if (basket.equals(map)) {
            answer++;
        }
    }

    return answer;
}

풀이 2 실행결과