카카오 블라인드 2021) 메뉴 리뉴얼

문제 해석을 잘못해서 푸는데 오래걸렸다.

세트 메뉴의 갯수가 같을 때, 주문한 수가 가장 많은 세트로 답을 구해주어야 한다.

처음에는 반대로 주문한 수가 많은 것들을 모아서, 세트 메뉴가 가장 많은 것을 답으로 리턴해주었다..

 

이외에도, 주문받은 메뉴를 정수형 배열의 인덱스에 저장하며, 입력받은 course에 따라 리턴해주는 방법도 시도했었지만, 당연히 틀리는 방법이다. (문제 해석을 잘못해서 카운팅만 해주면 된다고 생각했었다.. ㅠ)

 

각설하고, 여러 차례 시도했는데 계속 틀려서 카카오 해설 힌트를 보고 permutation을 적용했다.

이 때, 미리 메뉴를 정렬해서 하는 방법이 더욱 효율적이겠지만, 처음에 비트마스크로도 접근을 했었어서, 이 코드를 지우기 아까워서 재활용했다. (효율적인 방법이라고는 말할 수 없다. 비트마스크로 변환하고 문자열로 다시 변환하는 과정이 permuation만큼 동작하기 때문에)

왠만하면, 정렬을 통해 미리 메뉴 순서를 정렬해주는 방법을 추천한다.

 

permutation이 끝나면, 해당 메뉴 조합을 리스트에 담아두었다.

 

이후, 이 리스트를 돌면서, 만들고자 하는 세트 메뉴의 비트마스크와 주어진 메뉴 주문서의 비트마스크의 and 연산을 통해, 유효한 경우가 몇 번인지 확인해서, 최소 주문 횟수인 2번 보다 크면, 해당 메뉴의 길이를 key로 세트 메뉴를 value로 HashMap에 저장해주었다.

 

위에서 저장된 HashMap을 가지고, 각 메뉴들의 길이들 중 주문한 수가 가장 많은 메뉴들을 List에 담은 다음 배열에 담아 return 해주어 문제를 풀었다.

 

bitmask과정을 없애고 사전에 메뉴를 sorting하면 코드도 더 간결하고 쉽게 풀 수 있는 문제다.

비트마스크는 코드가 아까워서 연습용으로 적용시켰다고 생각한다.. 

문제 풀이의 핵심은 사전 정렬, permutation, HashMap의 활용 정도라고 볼 수 있다.

 

 

코드

import java.util.*;

public class Solution {
  final char EXIST = '1';
  final int ASCII_UPPER_START = 'A';
  final int MIN_MENU =2;
  final int PERMUTATION_START_INDEX =0, DEFAULT_BITMASK =0, DEFAULT_COUNT =0;

  List<String> permutationList;
  Map<Integer, List<Menu>> answerMap;

  public String[] solution(String[] orders, int[] course) {
    initAnswerMap(course);
    permutationList = new ArrayList<>(); // 초기화
    for(String order : orders) {
      char[] orderArr = order.toCharArray();
      permutation(orderArr,PERMUTATION_START_INDEX, DEFAULT_BITMASK, DEFAULT_COUNT); // 메뉴 조합 생성
      setAnswerMap(orders, course); // permutation에 있는 메뉴 세트가 다른 order와 몇 개나 일치하는지 확인
      permutationList.clear();
    }

    return getAnswerArr(course);
  }

  private void initAnswerMap(int[] course) { // 여기가 잘못됨, 동길이일때, 가장 많이 주문된 것을 출력해야함 (가장 많은 것 중 가장 긴 길이가 아니라)
    answerMap = new HashMap<>();
    for(int courseNumber : course) {
      answerMap.put(courseNumber, new ArrayList<>());
    }
  }

  private void permutation(char[] order, int index, int bitMask, int count) {
    if(count >= MIN_MENU) {
      String menu = parseUpperString(bitMask);
      if(!permutationList.contains(menu)) {
        permutationList.add(menu);
      }
    }
    if(index == order.length) {
      return;
    }

    permutation(order, index+1, bitMask|(1<<order[index]-ASCII_UPPER_START), count+1);
    permutation(order, index+1, bitMask, count);
  }

  private void setAnswerMap(String[] orders, int[] course) {
    for(String menu : permutationList) { // 각 메뉴가 몇개나 일치하는지 카운팅
      int len = menu.length();
      if(!isCourse(len, course)) {
        continue;
      }

      int count =0;
      int origin = parseBitMask(menu);
      for(String order : orders) { // 다른 메뉴들이랑 비교
        int target = parseBitMask(order);
        if((origin&target) == origin) { // 되는 메뉴 카운팅
          count++;
        }
      }

      if(count >=MIN_MENU) {
        List<Menu> list = answerMap.get(len);
        list.add(new Menu(menu, count));
        answerMap.replace(len, list);
      }
    }
  }

  private String parseUpperString(int bitMask) {
    String menuBinary = Integer.toBinaryString(bitMask);
    int len = menuBinary.length();
    StringBuilder sb = new StringBuilder();
    for(int i=0; i<len; i++) {
      if(menuBinary.charAt(len-i-1) == EXIST) {
        sb.append(getChar(i));
      }
    }
    return sb.toString();
  }

  private boolean isCourse(int count, int[] course) {
    for(int courseNumber : course) {
      if(count == courseNumber) {
        return true;
      }
    }
    return false;
  }

  private int parseBitMask(String order) {
    char[] orderArr = order.toCharArray();
    int bitMask =0;
    for(char ch : orderArr) {
      bitMask |= (1 << ch-ASCII_UPPER_START);
    }
    return bitMask;
  }

  private char getChar(int ascii) {
    return (char)(ascii+ASCII_UPPER_START);
  }


  private String[] getAnswerArr(int[] course) {
    List<String> answerList = new ArrayList<>();

    for(int courseNumber : course) {
      List<Menu> menuList = answerMap.get(courseNumber);
      Collections.sort(menuList);
      int prev = menuList.size() ==0 ? 0 : menuList.get(0).count;
      for(Menu menu : menuList) {
        if(prev != menu.count) {
          break;
        }
        if(!answerList.contains(menu.menus)) {
          answerList.add(menu.menus);
        }
      }
    }

    String[] answerArr = new String[answerList.size()];
    for(int i=0; i<answerList.size(); i++) {
      answerArr[i] = answerList.get(i);
    }
    Arrays.sort(answerArr);
    return answerArr;
  }

  private class Menu implements Comparable<Menu> {
    String menus;
    int count;

    public Menu(String menus, int count) {
      this.menus = menus;
      this.count = count;
    }

    @Override
    public int compareTo(Menu menu) {
      return menu.count - this.count;
    }
  }
}