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

소요시간

약 30분.
문제 이해하는 데에 5분. 이해하자마자 바로 누적합이 떠올랐다.
그리고 바로 코딩 시작. 전체적으로 다 짜는데에 15분 정도 걸림
테스트 케이스 하나는 통과 못해서 왜일까 고민하다가 누적합의 인덱스를 잘못 접근하고 있었음. 이후 오류 발견후 수정.

문제해결 과정

사용한 자료구조 및 알고리즘 : 누적합, 해시맵

해시맵을 사용한 이유 : 나중에 배열을 사용할 건데 예를 들어 바나나의 경우에는 arr의 인덱스에 바나나가 올 수 없으므로 바나나를 0의 인덱스로 치환하는데에 사용.
누적합을 사용한 이유: 효과적이고 빠르게 구간합을 얻기 위함.

예상한 시간 복잡도 :
want 의 길이를 n, discount 의 길이를 m이라고 한다면
O(nm) 이 걸릴것으로 예상. want의 길이가 10까지, discount의 길이가 100,000까지니 최대 1,000,000 이 걸릴 것이고 이는 대략 0.01 초에 해당.

풀이 과정

소스코드에 주석으로 달았다.
내가 가장 많이 고민한 부분이 코드 거의 마지막 부분에 if와 else if 로 나눈 부분이다. 이 때의 if 문이 예외처리 한 것인데, arr[i-allDay][j] 를 했을 때 [i-allDay] 가 -1이 될 때가 있었으므로, 이게 -1이라면 굳이 빼주지 않아도 된다. 그래서 이 경우에는 빼주지 않도록 한 것이 예외처리이다.

소스코드

import java.util.*;
class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        HashMap<String,Integer> item=new HashMap<>();
        int index=0;
        // 해시맵에 각 want 물품들을 인덱스로 치환하여 저장.
        for(int i=0;i<want.length;i++){
            item.put(want[index],index);
            index++;
        } 
        //배열 선언 후 discount[0]의 물품의 누적합을 1로 함. 하지만 이것이 want에 없는 물품일 
        //수 있으므로 if문으로 want 에 있는 물품일 때만 누적합을 1로 만든다.
        int arr[][]=new int[discount.length][want.length];
        if(item.containsKey(discount[0])==true) arr[0][item.get(discount[0])]=1;
        
        for(int i=1;i<discount.length;i++){
            for(int j=0;j<arr[0].length;j++){ 
                arr[i][j]=arr[i-1][j];
            } 
            //만약 discount[i] 의 물품이 want에 없는 물품이라면 누적합을 구할 필요 없음.
            if(!item.containsKey(discount[i])) continue; 
            //있는 물품이라면 누적합 추가.
            arr[i][item.get(discount[i])]++;
        }
        //소요 일수. number[i] 를 다 더함.
        int allDay=0;
        for(int i=0;i<number.length;i++)
            allDay+=number[i];
        
        int count =0;
        for(int i=allDay-1;i<discount.length;i++){
            boolean n=true; 
            for(int j=0;j<want.length;j++){
                if(i-allDay<0){  //소요 일수를 빼줬을 때의 값을 빼줘서 이게 일치하지 않으면 false
                    if(arr[i][j]!=number[j]) n=false;
                } 
                else if(arr[i][j]-arr[i-allDay][j]!= number[j]) 
                    n=false;
            }
            if(n) count++; //false 가 되지 않았다면 일치하는 거니 count 증가
        }
        
        return count;
    }
}

회고

프로그래머스에 있는 카카오 문제중에서 해시맵을 사용해야하는 문제들이 꽤 많다고 느꼈다. 물론 아직 레벨 2 수준이어서 그런 것일 수도 있지만그만큼 해시맵에 대한 개념이 중요하다는 것 아닐까?

하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212