[프로그래머스] 메뉴 리뉴얼

이문제는 2019년 카카오 블라인드 테스트에 나왔던 문제고 레벨2로 분류가 되어있지만 꽤 어려웠다..

 

문제 ) 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

 

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

 

 

기본적으로 필요한 지식인 조합 구하기에 대해서 공부가 필요하다.

 

 

---

조합(Combination) : 조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말한다.

예를 들어 [1, 2, 3] 이란 숫자 배열에서 2개의 수를 순서 없이 뽑으면

[1, 2] [1, 3] [2, 3]

이렇게 3 개가 나온다.

 

 

조합 구현과 관련해 아주 좋은 포스팅이 있어서 이곳 을 참고했다.

이 포스팅에 백트래킹을 이용한 구현, 재귀방식을 사용한 구현 

두가지 예시가 있는데 나는 백트래킹 방식을 사용해보기로 했다.

---

arr : 배열

visited : 각 원소를 선택하는지, 선택하지않는지 저장

start : 기준. start보다 큰 index만 뽑을 후보가 된다

n : 배열의 길이

r : 조합의 길이

    // 백트래킹 사용
    // 사용 예시 : combination(arr, visited, 0, n, r)
    static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

 

함수 호출시 r 에 몇개를 뽑을건지 갯수를 넣으면, 함수가 재귀적으로 호출될때 1씩 줄여나가게 되고,

최종적으로 r에 0이 들어왔을때 해당 조합을 출력해주면 된다.

visited 배열에 지금 선택한 조합이 어떤 어떤 원소를 넣고 뺄지에 대한 정보가 담겨있는 것이다.

(선택하면 1, 선택하지 않으면 0 저장)

 

for문의 수행을 보면, 각각의 배열원소가 선택된 경우 / 선택되지 않은 경우 를 전부 탐색할수 있게된다.

---

출력은 이런식으로 하면 된다.

 

    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }

---

이를 참고해서 우선, 문제의 입력값 String 배열에서 2개의 알파벳을 선택하는 모든 조합을 출력하는 코드를 작성해보았다. String 이기 때문에 arr[i] 로 접근하는것이 아닌, str.toChar(i) 로 접근을 하는 것 제외하고는 전부 동일했다.

 

 

만들어진 조합을 정렬을 하고, 

Hash Map 에 저장해서 중복이 몇개나 있는지 체크한다음

가장 많은 케이스만 내림차순으로 출력을 하면 될것 같다.

 

이런 문제를 어떻게 그런 짧은시간내에 풀수있단말인가ㅜㅜ

무척 절망적이지만, 그래도 Combination에 대해 알아두는 것은 여러모로 쓰임새가 많을것같다.

 

 

참고로,

Permutaion 의 경우 C++에 기본적으로 제공되기 때문에 이내용도 정리해둔다.

아쉽게도 Combination은 JAVA와 마찬가지로 재귀함수등을 사용해 구현해야한다.

 

	vector<int> v = { 10, 5, 1, 2, 4 };
	int len = v.size();
	//sort(v.begin(), v.end());	// 정렬 후 next_permutation 사용해야함
	do {
		for (int i = 0; i < len; i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
	} while (next_permutation(v.begin(), v.end()));

 

 

Hash Map을 사용해서 배열에 중복된 값이 몇개있는지 세는 쉬운 방법은 아래와 같다.

(이곳을 참고)

 

map.put(key, map.getOrDefault(key, 0)+1);

put을 할때 이미 그 key가 있으면 그 value에 1을 더해주고, 아니면(최초삽입인 경우) value는 1이 된다.

 

Integer getOrDefault(Object key, Integer defaultValue) : key값이 있으면 해당 key의 value를 반환하고 없으면 default값을 반환한다.

 

 

 

최종 코드)

import java.util.HashMap;
import java.util.Map;
import java.util.Collections;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        List<String> testList = new ArrayList<String>();
        for(int r = 0; r<course.length; r++){
            HashMap<String, Integer> map = new HashMap<>();
            for(int i=0; i< orders.length; i++){
                boolean[] visited = new boolean[orders[i].length()];
                combination(orders[i], visited, 0, orders[i].length(), course[r],map);
            }
            if(map.size() > 0){
                int maxValue = Collections.max(map.values());
                for(Map.Entry<String, Integer> m : map.entrySet()) {
			        if(m.getValue()==maxValue && maxValue>=2) {
                        testList.add(m.getKey());
                    }
			    }
            }
        }
        Collections.sort(testList);
        answer = new String[testList.size()];
        int cnt = 0;
        for(String item : testList){
            answer[cnt++] = item;
        }
        return answer;
    }
    static void combination(String arr, boolean[] visited, int start, int n, int r, HashMap<String, Integer> map)       {
        if(r == 0) {
            String res = print(arr, visited, n);
            
            char[] tmp = res.toCharArray();
            Arrays.sort(tmp);
            
            res = String.valueOf(tmp);
            map.put(res,map.getOrDefault(res,0)+1 );
            
            return;
        } 

        for(int i=start; i<n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1, map);
            visited[i] = false;
        }
    }
    static String print(String arr, boolean[] visited, int n) {
        String result = "";
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                result += arr.charAt(i);
            }
        }
        return result;
    }
}

 

문제의 최종적인 풀이는 위와 같다.

너무 오래 걸려서 사실상 푼것보다 공부를 했다는 것에 의의를 두어야할것 같다.

항상 그렇지만 java에서 answer 가 String 배열로 주어지는 경우에 값을 자유자재로 넣기가 너무 힘들어진다..

굳이 굳이 ArrayList에 옮겼다가 다시 string으로 옮기고 했는데

이과정이 필요없는지는 다시 한번 확인해봐야겠다.

어쨋건 Combination을 구한 이후부터는 혼자힘으로 완수를 해서 기분이 좋다!

 

 

추가로 Collection 함수를 호출했다.

 

Collections.sort(testList);

Collections.max(map.values());

 

sorting을 하기도 하고 최댓값을 찾기도 하고 간편하게 사용할 수 있다.

함수 인자로는 List 형이면 되기 때문에 map.values()처럼 map의 value값만 list로 만들어주는 함수를 써서

value중의 최댓값을 찾을수 있었다.

(map은 결국에 찾은 최대value값 바탕으로 한번 순회를 돌아야하는데, 이건 중복된 최댓값이 존재하기 때문에 어쩔수 없었던 것 같다)