완전탐색

프로그래머스 2023 KAKAO BLIND RECRUITMENT Level 2 문제 이모티콘 할인행사를 java를 이용하여 풀어보았다.
처음 봤을 때부터 최악의 경우를 가정하니 1억번을 넘지 않았고 완전 탐색으로 풀면 되겠다는 확신을 가졌다.

문제 링크 첨부한다.
https://school.programmers.co.kr/learn/courses/30/lessons/150368

---

모든 케이스 구하기

문제의 핵심은 다음과 같다.

몇 개의 이모티콘이든지, 각 이모티콘이 10,20,30,40 퍼센트의 할인율을 갖는 모든 경우의 수를 다 따져주기

만약 이모티콘의 종류가 2개라면 다음과 같다.
(10,10), (10,20), (10,30), (10,40), (20,10),(20,20),(20,30),...(40,20),(40,30),(40,40) 과 같이 총 4(할인율 종류)의 2(이모티콘 종류)제곱만큼의 경우의 수가 나오는 것이다.

제한 사항에서 이모티콘의 종류는 7가지라고 했기 때문에 기껏해봐야 4의 7제곱의 경우가 나올테고 이는 2의 14제곱, 즉 1만 6천개 정도의 경우의 수가 나오기 때문에 어차피 1억번이 넘지 않아 시간 초과는 걱정할 필요가 없다.

그렇다면 중요한 것은 모든 경우의 수를 어떻게 구해줄 것이냐는 것이다.

---

재귀

재귀함수를 이용해 DFS 를 구현했다. 처음에 내가 바로 풀지 못하고 헛짓을 했던 부분이 있다. 재귀를 이용해서 조합을 구하는 경우가 이전에 몇 차례 있었기 때문에 재귀가 나오자 플란다스의 개마냥 "헥헥 조합이다 조합이다!!!!!" 하며 쓸 데 없는 boolean[] visited 를 선언하고 i번째 이모티콘에 대해 10,20,30,40 퍼센트 할인율을 이미 때린 전적이 있는지를 체크한 것이다. 당연히 불필요한 계산들을 하게 됐고 어찌저찌 테스트케이스 20개 중 3개만 통과하지 못해서 계속 그 풀이에 매달렸다.

어차피 10,20,30,40 싹 다 적용해주는 완전 탐색이지 n개 중 r개를 구하는 조합이 아닌데 이상한 프레임에 스스로 가둬놓고 한참을 헤맸다.

다음은 ArrayList<int[]> saleCases에 가능한 모든 할인율 경우를 추가해주는 메소드다.

static void dfs(int curEmoji, int n, int[] saleCase){
	if(curEmoji==n){
		int[] tmp = new int[saleCase.length];
		for(int i=0; i<saleCase.length; i++)
			tmp[i] = saleCase[i];

		saleCases.add(tmp);
		return;
	}

    for(int i=0; i<4; i++){
		saleCase[curEmoji] = saleType[i];
		dfs(curEmoji+1, n, saleCase);
	}
}

---

구매 금액 계산 및 이용권 구매 여부 판단

여기서부터는 그냥 문제의 조건에 따라 착실하게 계산을 해주면 된다. 다른 풀이들을 보니 더 짧고 예쁘게 작성한 사람도 있던데 나는 시험장에서 시간에 쫓기며 바로 머릿속에 떠오르는 대로 빠르게 작성한다는 관점에서 작성했다. 위의 모든 케이스를 구하는 부분에서는 막혀서 시간이 오래 걸렸지만 이 부분은 쉬지 않고 생각나는 대로 작성했다.

/* 이용자별 구매 케이스 구하기 */
ArrayList<int[]> resList = new ArrayList<>();
int[][] userInfoAry = new int[users.length][2]; // 0번이 0이면 이용권 X, 1이면 이용권 O. 1번은 구매금액. 0번이 1이 되는 순간 1번은 자동으로 0으로 변환.

for(int[] saleInfo: saleCases){
	for(int i=0; i<emoticons.length; i++){
		int thisEmojiSale = saleInfo[i];
		int thisEmojiPrice = emoticons[i] * (100-thisEmojiSale) / 100;
		for(int j=0; j<users.length; j++){
			if(users[j][0]<=thisEmojiSale){ // 기준 넘어서 돈 주고 삼
				userInfoAry[j][1] += thisEmojiPrice;
			}
		}
	}

	/* 하나의 result 경우가 종합되었고 정산해서 resList 에 하나 추가해야 함. */
	int signups = 0;
	int totalSales = 0;
	for(int i=0; i<users.length; i++){
		if(users[i][1]<=userInfoAry[i][1]){
			signups++;
		}
		else{
			totalSales += userInfoAry[i][1];
		}
	}
	resList.add(new int[]{signups, totalSales});

	userInfoAry = new int[users.length][2]; // 초기화
}

---

우선순위 정렬해주기

resList 가 완성됐다. 이제 문제의 조건대로 이용권 구매자수를 우선순위로 내림차순 정렬한 후에, 구매 금액별로 다시 내림차순해주면 된다.
매번 Comparator를 사용해서 정렬해주는 문법을 잊어먹는다. 언젠가는 반드시 다 외워서 치는 날이 오겠지...? 적어도 코테날에는 외워칠 수 있게 지금 확실하게 공부하자,,,
resList의 원소 int[]의 0번 요소 기준으로 정렬 후 1번 요소 기준으로 정렬해주면 된다. 이는 다음과 같다.

/* resList 문제 조건대로 정렬해주기 */
resList.sort(new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
		if (o1[0] != o2[0]) return o2[0] - o1[0];
		else return o2[1] - o1[1];
	}
});

---

다음은 내가 제출한 전체 코드다.

import java.util.*;

public class 이모티콘할인행사 {

    public static void main(String[] args) {

//        System.out.println(Arrays.toString(solution(new int[][]{{40, 10000}, {25,10000}}, new int[]{7000,9000})));
        System.out.println(Arrays.toString(solution(new int[][]{{40, 2900}, {23, 10000}, {11, 5200}, {5, 5900}, {40, 3100}, {27, 9200}, {32, 6900}}, new int[]{1300, 1500, 1600, 4900})));
    }

    static int[] saleType = {10,20,30,40};
    static ArrayList<int[]> saleCases = new ArrayList<>();

    static int[] solution(int[][] users, int[] emoticons) {

        /* 이모티콘별 할인율 경우의 수 리스트 만들어주기 */
        dfs(0, emoticons.length, new int[emoticons.length]);

        /* 이용자별 구매 케이스 구하기 */
        ArrayList<int[]> resList = new ArrayList<>();
        int[][] userInfoAry = new int[users.length][2]; // 0번이 0이면 이용권 X, 1이면 이용권 O. 1번은 구매금액. 0번이 1이 되는 순간 1번은 자동으로 0으로 변환.

        for(int[] saleInfo: saleCases){
            for(int i=0; i<emoticons.length; i++){
                int thisEmojiSale = saleInfo[i];
                int thisEmojiPrice = emoticons[i] * (100-thisEmojiSale) / 100;
                for(int j=0; j<users.length; j++){
                    if(users[j][0]<=thisEmojiSale){ // 기준 넘어서 돈 주고 삼
                        userInfoAry[j][1] += thisEmojiPrice;
                    }
                }
            }

            /* 하나의 result 경우가 종합되었고 정산해서 resList 에 하나 추가해야 함. */
            int signups = 0;
            int totalSales = 0;
            for(int i=0; i<users.length; i++){
                if(users[i][1]<=userInfoAry[i][1]){
                    signups++;
                }
                else{
                    totalSales += userInfoAry[i][1];
                }
            }
            resList.add(new int[]{signups, totalSales});

            userInfoAry = new int[users.length][2]; // 초기화
        }

        /* resList 문제 조건대로 정렬해주기 */
        resList.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) return o2[0] - o1[0];
                else return o2[1] - o1[1];
            }
        });

        return resList.get(0);
    }

    static void dfs(int curEmoji, int n, int[] saleCase){
        if(curEmoji==n){
            int[] tmp = new int[saleCase.length];
            for(int i=0; i<saleCase.length; i++)
                tmp[i] = saleCase[i];

            saleCases.add(tmp);
            return;
        }

        for(int i=0; i<4; i++){
            saleCase[curEmoji] = saleType[i];
            dfs(curEmoji+1, n, saleCase);
        }
    }
}

---

마치며

이 문제가 Level 3이라고 잘못 보고 들어갔다. 그래서 풀면서 무려 Level 3이라는 압박감에 엄청나게 복잡하고 어려운 구현이 반드시 수반될 거라는 두려움이 있었다. 그래서 이전에 내가 어렵게 풀었던 조합, 백트래킹 문제들이 생각났나보다. 직전에 풀었던 택배 배달과 수거하기 문제처럼 그냥 이 문제는 어떻게 해결하는 게 가장 좋을까? 라는 질문을 던지고, 주어진 문제 자체에 집중하며 고민해야 하는데 계속 예전에 풀었던 문제들로부터 도움을 받으려고 하니까 스스로 이상한 프레임에 가두는 꼴이 된다.
문제 해결 자체에 자신감을 키우기 위해서는 머리를 자주 싸매는 수밖에 없는 것 같다.