Java - [프로그래머스 Lv.2]72411 - 메뉴 리뉴얼

출처

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

프로그래머스

 

문제

 

개인적으로 처음에 잘 안읽어서 그런지 좀 헷갈렸던 문제였습니다. 문제를 요약하자면,

 

1. 단품으로 1개씩 파는 레스토랑이 있는데, 2개 이상 묶어서 코스 요리로 만들려고 한다.

2. 단, 코스 요리는 2개 이상의 요리로 구성되어 있으며, 적어도 2명의 손님이 시켜먹은 조합이여야 한다.

  - 예를들어, 1번 손님은 A, C, D 조합으로 먹었고 2번 손님이  A, D 조합으로 먹었다면, (A, D) 조합이 코스 요리 후보가 될 수 있다.

3. 문제에는 배열에 코스요리에 포함될 음식의 갯수를 담아준다. 이것 중 가장 많이 사람들이 주문한 것을 코스 요리로 제작한다.

  - course 배열이 [2, 3, 4]로 주어진다면, 각각 2, 3, 4개의 음식의 조합으로 구성된 코스요리를 만들어야 한다.

  - 만약, 2개의 음식을 2명 이상이 주문한 조합이 (A, D)  -> 3명이 먹음, (A, C) -> 2명이 먹음 이라면 (A, D)이 코스요리가 된다.

  - 위의 예제에서, (A, D) 와 (A, C)가 3명 동점으로 사람들이 제일 많이 먹은 조합이라면, 두개 모두 코스요리가 된다.

 

한마디로, 사람들이 시켜먹은 음식들로 만들 수 있는 모든 조합 중, 가장 많이 사람들이 선택한 조합을 동점을 허용하여 구하는 문제입니다.

 

풀이

원래 파이썬으로 코테를 준비했을 시절에는 combination 으로 간단하게 구했던 문제인데, 자바로 바꾸면서 직접 구현하려니까 영 불편했습니다...

 

자바에서 조합은 DFS와 BackTracking 등으로 구현할 수 있습니다. 이번 문제는 중복을 허용하지 않고, 순서와 관계 없이 조합을 구하는 문제이기 때문에  BackTracking은 적용하지 않고 DFS만 적용하여 해결할 수 있습니다.

 

코드와 함께 살펴보도록 하겠습니다.

Map<String, Integer> map = new HashMap<>();
int[] max;	
    
public String[] solution(String[] orders, int[] course) {
    List<String> answer = new ArrayList<>();
        max = new int[course.length];

        for (String x: orders) {
            char[] charArr = x.toCharArray();
            Arrays.sort(charArr);
            String str = String.copyValueOf(charArr);
            for (int i = 0; i < course.length; i++) {
                dfs(str, "",0 ,i ,course[i]);
            }
     
     . . .
         
 }

 

먼저, 모든 메뉴 조합(ex. "AC'")들에 대해 사람들이 몇번 시켜 먹었는지를 기록해주어야 합니다. 때문에 문자열을 key로 가지고, 횟수를 value로 기록할 수 있는 Map 구조체를 하나 global 변수로 선언하였습니다.

 

int형 배열도 하나 선언 해주었습니다. 이 배열은 우리가 코스로 만들어야하는 음식의 수가 담긴 course에 대응하여, 각 숫자에 대해 최대 시켜먹은 횟수를 기록해주는 배열입니다.

  - (ex. course[0] = 2 -> max[0] = 3 : 2개의 음식으로 만든 조합은 3명의 사람이 먹었으며, 이것이 최대값임을 기록) 

 

문제에서 사람이 먹은 음식을 "ABCD" 처럼 친절하게 순서대로 주지 않고 역순으로 "CBA"와 같이 제공됩니다. 결과로 만든 코스요리는 "ABC"여야 하는데 역순으로 되어있으면 조합을 생성할때 불편하기 때문에, 순서대로 문자열을 재정렬 하는 과정이 필요합니다. char 배열로 바꾸어 정렬한 뒤, 다시 스트링으로 변환하는 과정을 넣어줍니다.

 

이제 course에 들어있는 코스 음식의 갯수대로 조합을 만들며 DFS()를 진행합니다.

 

public void dfs(String arr, String str, int start, int locate, int len) {
        
    // 종료 조건
    if (str.length() == len) {
        map.put(str, map.containsKey(str) ? map.get(str) + 1 : 1);
        max[locate] = Math.max(max[locate], map.get(str));
    }

    for (int i = start; i < arr.length(); i++) {
        dfs(arr, str + arr.charAt(i), i + 1, locate, len);
    }
}

 

재귀 호출을 하는 함수는 항상 종료조건이 중요하며, 가장 먼저 작성하면 편합니다. 

 

Dfs를 진행하며 조합을 만드는 이 함수는, 매개변수 5개를 받습니다.

• arr : 현재 탐색하는 손님이 시킨 메뉴가 적힌 문자열
• str : 현재까지 만들어진 메뉴의 조합이 적힌 문자열
• start: 다음 탐색을 진행할 위치를 저장합니다. 문자열 0번째의 음식을 조합에 추가하였다면, start는 1이 되며, 1 위치부터 조합을 추가하며 재귀호출을 진행합니다. (start 이전의 문자에 대해서는 탐색을 진행하지 않음. AC와 CA는 중복되기 때문)
• locate: 현재 course의 몇번째 원소의 코스요리를 만들고 있는지 저장합니다. max[locate]에 최대값을 저장하기 위함입니다.
• len : 지금 만들 조합의 최대 길이 입니다. len과 현재까지 만든 조합의 수가 동일하다면, map에 값을 갱신하고 max에 최대값을 저장 후 dfs가 종료됩니다.

map은 key의 중복을 허용하지 않습니다. 때문에 key가 존재 하지 않는다면 1으로 put을 하고, key가 이미 존재한다면 기존 value에 1을 더해 다시 put을 한다면 업데이트가 자동으로 진행됩니다.

 

이제, 조합과 횟수를 다 구했다면 마지막으로 정답을 구합니다.

	. . .
    
    for (Map.Entry<String, Integer> x : map.entrySet()) {
            for (int i = 0; i < course.length; i++) {
                if (x.getKey().length() == course[i] && max[i] >= 2 && max[i] == x.getValue()) {
                    answer.add(x.getKey());
                }
            }
        }

        return answer.stream().sorted().toArray(String[]::new);
        
    }

 

map.entrySet()를 통해 map에 들어있는 key와 value 쌍을 받을 수 있습니다. 반복문을 통해 2명 이상이 주문했는지, 최대 값과 동일한지를 살피고 맞다면 List에 넣어줍니다.

 

마지막으로 stream 메서드를 통해 정렬 후 Array로 변환하여 리턴합니다.

 

전체 코드

import java.util.*;

class Solution {
    
    Map<String, Integer> map = new HashMap<>();
    int[] max;
    
    public String[] solution(String[] orders, int[] course) {
        List<String> answer = new ArrayList<>();
        max = new int[course.length];
        
        for (String x: orders) {
            char[] charArr = x.toCharArray();
            Arrays.sort(charArr);
            String str = String.copyValueOf(charArr);
            for (int i = 0; i < course.length; i++) {
                dfs(str, "",0 ,i ,course[i]);
            }
            
        }
        for (Map.Entry<String, Integer> x : map.entrySet()) {
            for (int i = 0; i < course.length; i++) {
                if (x.getKey().length() == course[i] && max[i] >= 2 && max[i] == x.getValue()) {
                    answer.add(x.getKey());
                }
            }
        }

        return answer.stream().sorted().toArray(String[]::new);
    }
    
    public void dfs(String arr, String str, int start, int locate, int len) {
        
        if (str.length() == len) {
            map.put(str, map.containsKey(str) ? map.get(str) + 1 : 1);
            max[locate] = Math.max(max[locate], map.get(str));
        }
        
        for (int i = start; i < arr.length(); i++) {
            dfs(arr, str + arr.charAt(i), i + 1, locate, len);
        }
    }
}