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

문제 보기

반복문에서 list를 순회하며 삭제할 때는 삭제 후 인덱스를 1 빼줘야 한다.

풀이

• 조합을 구하기 위하여 DFS를 사용
• 코스요리와 해당 코스요리 count를 저장하기 위해 Map 사용
  
  
• order를 오름차순으로 정렬 후 모든 조합을 구하기 위해 dfs() 시작
• 조합이 완성되면 코스요리에 포함된 메뉴 수가 2개 이상인 경우만 map에 value 1로 저장하거나 key가 존재하면 value 1 증가
• keySet을 List로 변환 후 반복문을 돌며 조건과 일치하지 않으면 List에서 삭제
  • 코스요리 count가 2보다 작은 경우
  • 예전 코스요리의 메뉴 수와 동일한데 현재 코스요리의 count가 더 높으면 예전 코스요리 삭제
  • 현재 코스요리의 count가 더 낮으면 현재 코스요리 삭제
• List를 알파벳 사전 순으로 정렬 후 반환

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

class Solution {

    public String[] solution(String[] orders, int[] course) {
        Map<String, Integer> map = new HashMap<>();
        for (String order : orders) {
            order = sortString(order);
            dfs(new boolean[order.length()], order, 0, course, map);
        }
        List<String> keySetList = new ArrayList<>(map.keySet());
        for (int i = 0; i < keySetList.size(); i++) {
            String key = keySetList.get(i);
            if (map.get(key) < 2) {
                keySetList.remove(i--);
                continue;
            }
            for (int courseLength : course) {
                if (key.length() != courseLength) {
                    continue;
                }
                for (int j = 0; j < i; j++) {
                    String preKey = keySetList.get(j);
                    if (key.length() != preKey.length()) {
                        continue;
                    }
                    if (map.get(key) < map.get(preKey)) {
                        keySetList.remove(i--);
                        break;
                    } else if (map.get(key) > map.get(preKey)) {
                        keySetList.remove(j--);
                        i--;
                    }
                }
            }
        }
        Collections.sort(keySetList);
        return keySetList.toArray(new String[0]);
    }

    public void dfs(boolean[] visited, String order, int depth, int[] course,
        Map<String, Integer> map) {
        if (depth == order.length()) {
            String menu = "";
            for (int i = 0; i < order.length(); i++) {
                if (visited[i]) {
                    menu += order.charAt(i);
                }
            }
            if (menu.length() < 2) {
                return;
            }
            for (int courseLength : course) {
                if (menu.length() == courseLength) {
                    if (!map.containsKey(menu)) {
                        map.put(menu, 1);
                    } else {
                        map.replace(menu, map.get(menu) + 1);
                    }
                }
            }
        } else {
            visited[depth] = true;
            dfs(visited, order, depth + 1, course, map);
            visited[depth] = false;
            dfs(visited, order, depth + 1, course, map);
        }
    }

    public String sortString(String string) {
        char[] charArray = string.toCharArray();
        Arrays.sort(charArray);
        return String.valueOf(charArray);
    }
}