프로그래머스_할인 행사

💻 문제 출처 : 프로그래머스_할인 행사

👉 내가 작성한 답

import java.util.*;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        
        int answer = 0;
        
        Map<String, Integer> wantIndex = new HashMap<>();
        
        int[] count = Arrays.copyOf(number, number.length);
        
        for(int i = 0; i < want.length; i++) {
            wantIndex.put(want[i], i);
        }
        
        for(int i = 0; i <= discount.length - 10; i++) {
            
            boolean possible = true;
            
            for(int j = i; j < i + 10; j++) {
                Integer index = wantIndex.get(discount[j]);
                
                if(index == null || count[index] == 0) {
                    possible = false;
                    break;
                }
                count[index]--;
            }
            
            for(int k : count) {
                if(k != 0) possible = false;
            }
            
            if(possible) answer++;
            
            count = Arrays.copyOf(number, number.length);
        }
        
        return answer;
    }
}

• 📌 접근 방식
  • Map에 want 요소의 index를 value로 저장해서 탐색하기 용이하게 변경
  • for문으로 순회할 때 외부 for문은 0부터 discount.length - 10까지만 순회하면 되고(시작하는 인덱스), 내부 for문은 시작 인덱스부터 10을 더한 값 까지만 순회하면 됨
  • want 목록에 없는 값이 나오면 해당 날짜는 불가
  • count하는 배열을 선언해서 각 요소의 값이 0이 되는지, 안 되는지를 확인해서 전부 0이 되면 answer 증가
• 📌 문제 풀이 설명
  • int 변수 answer를 선언하고 0으로 초기화
  • String을 key로 갖고, Integer를 값으로 갖는 wantIndex라는 이름의 Map 생성
  • int 배열 count를 선언하고 number 배열의 값을 복사
  • for문으로 0부터 want의 길이 미만까지 1씩 증가하며 순회
    • wantIndex에 want[i]를 key로, i를 value로 넣어서 인덱스를 저장
  • for문으로 0부터 discount의 길이 - 10 이하까지 1씩 증가하며 순회
    • boolean 변수 possible을 선언하고 true로 초기화
    • for문으로 i부터 i + 10 미만까지 1씩 증가하며 순회
      • Integer 변수 index에 wantIndex에서 discount[j]에 해당하는 value를 넣음
      • 만약 index가 null이거나(해당 key가 없는 경우 = want 목록에 없는 요소) count[index]가 0이면(초과하는 경우)
        • possible에 false 대입
        • break로 해당 for문 종료
      • count[index]를 1 감소
    • 향상된 for문으로 count 순회
      • 만약 count의 요소가 0이 아니면 possible에 false 대입
    • 만약 possible이 true면 answer 1 증가
    • count에 다시 number 배열 복사
  • for문 종료 후 return answer
    
    
    
    

👉 다른 사람이 작성한 답

import java.util.*;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        
        int answer = 0;
        Map<String, Integer> wantIndex = new HashMap<>();
        for (int i = 0; i < want.length; i++) {
            wantIndex.put(want[i], i);
        }

        int[] windowCount = new int[want.length];
        for (int i = 0; i < 10 && i < discount.length; i++) {
            if (wantIndex.containsKey(discount[i])) {
                windowCount[wantIndex.get(discount[i])]++;
            }
        }

        if (isValid(windowCount, number)) {
            answer++;
        }

        for (int i = 10; i < discount.length; i++) {
            if (wantIndex.containsKey(discount[i - 10])) {
                windowCount[wantIndex.get(discount[i - 10])]--;
            }
            if (wantIndex.containsKey(discount[i])) {
                windowCount[wantIndex.get(discount[i])]++;
            }
            
            if (isValid(windowCount, number)) {
                answer++;
            }
        }

        return answer;
    }

    private boolean isValid(int[] windowCount, int[] number) {
        for (int i = 0; i < number.length; i++) {
            if (windowCount[i] < number[i]) {
                return false;
            }
        }
        return true;
    }
}

• 📌 접근 방식
  • 내가 구현한 코드에 슬라이딩 윈도우 기법을 적용
    • 슬라이딩 윈도우
      • 일정한 크기의 '윈도우'가 데이터의 시작부터 끝까지 이동하면서 특정 조건을 검사하거나 처리를 하는 방식
• 📌 문제 풀이 설명
  • int 변수 answer를 선언하고 0으로 초기화
  • String을 key로 갖고, Integer를 값으로 갖는 wantIndex라는 이름의 Map 생성
  • for문으로 0부터 want의 길이 미만까지 1씩 증가하며 순회
    • wantIndex에 want[i]를 key로, i를 value로 넣어서 인덱스를 저장
  • int 배열 windowCount를 want의 길이로 생성
    • 현재 윈도우(10일) 내에서 각 제품이 몇 번 할인되었는지 저장하는 배열
  • for문으로 0부터 10 미만까지 1씩 증가하며 순회
    • 만약 wantIndex에 discount[i]가 키로 있다면
      • windowCount의 discount[i]에 해당하는 key(인덱스)를 인덱스에 1 증가
      • ➕ 정현이가 원하는 제품들의 빈도를 나타내기 위해 만드는 배열로, 첫 10일에 정현이가 원하는 제품이 몇 번 나오는지 확인하기 위해 필요한 것
  • 만약 isValid 메서드에 windowCount와 number를 인수로 전달한 값이 true면 answer 1 증가
    • isValid 메서드
      • windowCount와 number 배열을 인자로 받음
      • for문으로 0부터 number의 길이 미만까지 1씩 증가하며 순회
        • 만약 windowCount[i]가 number[i] 보다 작으면 return false
      • for문 종료 후 return true
  • for문으로 10부터 disction의 길이 미만까지 1씩 증가하며 순회
    • 만약 wantIndex에 discount[i - 10]이 키로 있다면
      • windowCount에서 discount[i - 10]에 해당하는 인덱스의 값을 1 감소
      • ➕ 윈도우에서 맨 앞 부분이 빠져나가고 다음 부분을 넣으면서 윈도우를 한 칸씩 이동시키는 방식
        • 빠져나간 제품의 할인 횟수를 감소시키고, 새롭게 추가된 제품의 할인 횟수를 증가
    • 만약 wantIndex에 discount[i]가 키로 있다면
      • windowCount에서 discount[i]에 해당하는 인덱스의 값을 1 증가
    • 만약 isValid 메서드에 windowCount와 number를 인수로 전달한 값이 true면 answer 1 증가
  • for문 종료 후 return answer