[알고리즘] 프로그래머스 메뉴리뉴얼 :: 우유

https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

처음에 문제를 읽고 간단한 문제일줄 알았으나,, 생각보다 시간이 오래걸려서 피곤했던 문제였습니다. 집중력이 부족해서 그런가

코드 설명

str 문자열에서 course의 개수 만큼 뽑을 수 있는 경우의 수, 즉 조합을 뽑아내는 함수를 구현하는 것이 핵심인 문제입니다.

여기서 조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말하는데 알고리즘 문제를 풀면서 자주 등장하는 편이니 공부해두면 좋을듯 합니다. 
알고리즘에서 자주 쓰는 조합(Combination) 설명 참고

 public static void DFS(String str, StringBuilder sb, int start_idx, int current_idx, int course_len) {
        if (current_idx == course_len) {
            map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
            return;
        }

        for (int i = start_idx; i < str.length(); i++) {
            sb.append(str.charAt(i));
            DFS(str, sb, i + 1, current_idx + 1, course_len);
            sb.delete(current_idx, current_idx + 1);
        }
    }

orders 배열에 저장되 있는 str 변수를 course ( ex : 2,3,4.. ) 크기 만큼 자를수 있게 구현한 백트래킹 함수입니다.
start_idx 변수는 DFS 함수 내에서 잘랐 을때 시작 기준이 되는 인덱스를 의미하고
current_idx 변수는 시작기준이 되서 course_len 만큼 잘려나가는 도중에 현재 얼만큼 StringBuilder에 누적되서 잘려있냐를 의미하는 인덱스 변수입니다.
course_len 변수는 course 배열에 저장된 값을 입력받아 해당 크기만큼 조합의 경우의 수를 구하게 하는 변수입니다.

    for (int i = 0; i < orders.length; i++) {
        char[] charArr = orders[i].toCharArray();

        Arrays.sort(charArr);

        orders[i] = String.valueOf(charArr);
    }

여기서 String 배열을 toCharArray를 통해 다시 오름차순으로 재정렬 해준 이유는
입출력 예 3번 처럼 ["XYZ", "XWY", "WXA"]를  입력받는 경우
WX, XW 가 같은 메뉴 이지만 순서가 다름에 따라 다른 메뉴로 분류되기 때문에 이를 오름차순으로 정렬해줌으로서
순열(N에서 R을 골랐을 때 순서가 상관있는 경우의 수)이 아니라
조합(N에서 R을 골랐을 때, 순서가 상관없는 경우의 수 )으로
순서가 상관없게 만들기 위함입니다.

        for (int i = 0; i < course.length; i++) {

            map = new HashMap<>();
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < orders.length; j++) {
                StringBuilder sb = new StringBuilder();

                DFS(orders[j], sb, 0, 0, course[i]);
            }

            for (String key : map.keySet()) {
                if (map.get(key) >= 2 && map.get(key) >= max) {
                    max = Math.max(map.get(key), max);
                }
            }

            for (String key : map.keySet()) {
                if (max == map.get(key)) {
                    al.add(key);
                }
            }

            Collections.sort(al);
        }

메뉴 조합을 Key에 저장하고, 메뉴 조합의 카운트 (그 메뉴가 몇번 주문되었는지)를 Value에 저장하여
각 메뉴가 모두 주문되고 카운트가 끝났을 때 (DFS 함수가 종료되었을 때)
메뉴 주문이 2번이상이고, 그중에 가장 주문량이 많은 메뉴의 주문량을 max 변수에 저장하였습니다.
그렇게 저장된 max 변수만큼 주문이 들어온 메뉴를 ArrayList 에 저장하여
Collections.sort(al) 함수를 통해 다시 오름차순으로 재정렬하여 출력하였습니다

 

전체 코드

 

import java.util.*;

class Solution {

    static HashMap<String, Integer> map;

    public ArrayList<String> solution(String[] orders, int[] course) {
        ArrayList<String> al = new ArrayList<>();

        for (int i = 0; i < orders.length; i++) {
            char[] charArr = orders[i].toCharArray();

            Arrays.sort(charArr);

            orders[i] = String.valueOf(charArr);
        }

        for (int i = 0; i < course.length; i++) {

            map = new HashMap<>();
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < orders.length; j++) {
                StringBuilder sb = new StringBuilder();

                DFS(orders[j], sb, 0, 0, course[i]);
            }

            for (String key : map.keySet()) {
                if (map.get(key) >= 2 && map.get(key) >= max) {
                    max = Math.max(map.get(key), max);
                }
            }

            for (String key : map.keySet()) {
                if (max == map.get(key)) {
                    al.add(key);
                }
            }

            Collections.sort(al);
        }
        
        return al;
    }

    public static void DFS(String str, StringBuilder sb, int start_idx, int current_idx, int course_len) {
        if (current_idx == course_len) {
            map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
            return;
        }

        for (int i = start_idx; i < str.length(); i++) {
            sb.append(str.charAt(i));
            DFS(str, sb, i + 1, current_idx + 1, course_len);
            sb.delete(current_idx, current_idx + 1);
        }
    }
}