[프로그래머스/72411] 메뉴 리뉴얼(Java)

Question

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72411
• 분류 : 브루트포스
• 풀이 시간 : 150분
  • 문제 조건 하나를 못찾아서 시간 많이 걸렸다
  • 내가 내 코드에 헷갈려서 애먹었다.. 변수명 대충 짓지 말자

문제 해설

1. 손님들은 단품메뉴를 주문
2. 스카피는 단품메뉴를 조합해서 코스요리를 만드려고 함
3. 코스요리에 들어갈 단품 메뉴 기준
   • 각 손님들이 한번 주문할 때 가장 많이 함께 주문한 단품메뉴들
   • 코스요리 메뉴는 최소 2가지 이상의 단품메뉴
   • 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합
4. 새로 추가하게 될 코스요리의 메뉴 구성을 구하여라

Solution

풀이 접근 방법

1. 단품 메뉴들의 갯수가 담긴 배열 : course
   • course 배열에 들어있는 값 = 코스요리 메뉴구성 문자열의 길이
2. "만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return"
   • "가장 많이" : 길이가 같은 코스요리 메뉴가 있으면 더 많이 나온(빈도수가 높은) 메뉴만 고른다
     • 각 길의의 빈도수 최대값 알아야 함
   • "모두 배열에 담아" : 코스요리 메뉴 구성은 다르지만, 길이와 빈도수가 같으면 모두 정답 배열에 담음
3. "배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬"
   • 뽑힌 코스요리 메뉴는 모두 오름차순 정렬해서 비교
   • 즉, "WX"랑 "XW"는 같은 코스요리 메뉴로 취급한다
4. "최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함"
   • 코스요리 메뉴 조합(빈도수)이 2 이상이여야한다

정답 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class Main {
  static HashMap<String, Integer> courseComb;
  static HashMap<Integer, Integer> lenFrequency;

  public static void main(String[] args) {
    String[] orders = new String[] { "ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH" };
    int[] courses = new int[] { 2, 3, 4 };

    System.out.println(Arrays.toString(solution(orders, courses)));

    orders = new String[] { "ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD" };
    courses = new int[] { 2, 3, 5 };
    System.out.println(Arrays.toString(solution(orders, courses)));

    orders = new String[] { "XYZ", "XWY", "WXA" };
    courses = new int[] { 2, 3, 4 };
    System.out.println(Arrays.toString(solution(orders, courses)));

  }

  static String[] solution(String[] orders, int[] course) {
    // 정답 문자열 담을 리스트
    ArrayList<String> answer = new ArrayList<String>();
    // <단품메뉴 조합으로 얻은 코스요리 메뉴, 해당 메뉴가 나온 빈도수>를 담은 map
    courseComb = new HashMap<String, Integer>();
    // <코스요리 메뉴구성 문자열 길이, 해당 길이를 가진 메뉴의 빈도수 중 제일 큰 값>을 담은 map
    lenFrequency = new HashMap<Integer, Integer>();

    // 구해야하는 메뉴구성 길이 map에 초기화
    for (int c : course) {
      lenFrequency.put(c, 0);
    }

    // 각 손님이 주문한 단품메뉴들로
    for (String order : orders) {
      // 코스요리 구성하는 메뉴 개수만큼 조합을 구함
      for (int courseLength : course) {
        // 단품메뉴의 개수(길이)보다 구성해야하는 코스요리의 개수(길이)가 더 길면 제외
        if (order.length() >= courseLength) {
          comb(new boolean[order.length()], 0, courseLength, order);
        }
      }
    }

    // 구해진 단품메뉴의 모든 조합을 비교
    for (String newCourse : courseComb.keySet()) {
      int length = newCourse.length();

      // 해당 메뉴구성의 빈도수가 2 이상
      // && 같은 문자열의 길이를 가진 메뉴들 중 빈도수가 가장 높은 메뉴구성이 일때
      if (lenFrequency.get(length) >= 2 && lenFrequency.get(length) == courseComb.get(newCourse)) {
        answer.add(newCourse);
      }
    }

    // 메뉴 구성 문자열 오름자순 정렬
    answer.sort(null);
    return answer.toArray(new String[answer.size()]);
  }

  static void comb(boolean[] visited, int start, int pick, String order) {
    if (pick == 0) {
      StringBuilder newMenu = new StringBuilder();

      // 조합으로 뽑힌 메뉴들로 코스요리 메뉴(문자열) 구함
      for (int i = 0; i < visited.length; i++) {
        if (visited[i])
          newMenu.append(order.charAt(i));
      }

      // "AB"나 "BA"는 같은 코스요리이기 때문에
      // 뽑힌 코스요리 메뉴는 모두 오름차순 정렬해서 비교
      String sortedNewMenu = sortedString(newMenu.toString());

      // 전체 조합 Map에 뽑힌 코스요리 메뉴의 빈도수 갱신
      courseComb.put(sortedNewMenu, courseComb.getOrDefault(sortedNewMenu, 0) + 1);

      // 해당 코스요리 메뉴(조합)가 몇 번 나왔는지
      int frequency = courseComb.get(sortedNewMenu);
      // 코스요리 메뉴(조합)의 길이
      int length = sortedNewMenu.length();

      // 해당 길이(단품메뉴의 개수)의 최대값 알기 위해
      // 코스요리 메뉴 길이의 빈도수 갱신
      lenFrequency.put(length, Math.max(frequency, lenFrequency.get(length)));

      return;
    }

    // 조합
    for (int i = start; i < order.length(); i++) {
      visited[i] = true;
      comb(visited, i + 1, pick - 1, order);
      visited[i] = false;
    }

  }

  // 문자열을 오름차순 정렬한 값을 리턴
  static String sortedString(String s) {
    char[] stringChar = s.toCharArray();

    Arrays.sort(stringChar);

    return new String(stringChar);
  }

}

알.쓸.유.메(알아두면 쓸데있는 유용한 메소드)

Map.getOrDefault

java.util.Map
  
public V getOrDefault(Object key,V defaultValue)

• 찾고자하는 key 값이 map에 있으면 해당 key의 vlaue 반환, 없으면 defaultValue 반환