[알고리즘] 프로그래머스 2단계 - 메뉴 리뉴얼

프로그래머스 문제 링크

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

 

문제 설명

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.

order[] 배열에 고객이 주문한 음식이 String 배열로 담겨있고 String 배열에 각 캐릭터는 단품 음식을 의미합니다.

예시 "ABCFG "의 경우 "A" 단품 음식 "B" 단품 음식 ..."G" 단품 형태로 되어있으며 여기서 course[]라는 int 배열이 주어질때 이 값을 통해서

각 단품음식을 조합하여서 course에서 가장 많은 단품음식을 배열에 담아 리턴한다. 단 값이 같은 경우 배열에 같이 담고 최종 리턴시 알파벳 오름차순으로 리턴한다.

 

예시

orders[]

["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]

course[]

[2,3,4]

 

result
["AC", "ACDE", "BCFG", "CDE"]

  

    
    
    
    
  
import java.util.*;

public class Main {
    
    static HashMap<Integer, HashMap<String,Integer>> courseMap = new HashMap<>();

    public static void main(String[] args) {
    	// 예시 실행
        for (String item : solution(new String[]{"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"}, new int[]{2, 3, 4})) {
            System.out.println(item);
        }
    }


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

        // 맵 초기화
        for (int i = 0; i < course.length; i++) {
            courseMap.put(course[i], new HashMap<>());
        }
        
        // 문자열 캐릭터로 자른후 각 캐릭터별 재귀호출을 통해서 단어 생성
        for (int i = 0; i < orders.length; i++) {
            String[] alphabetSorted = alphabetSort(orders[i]);
            addCombinations(0, alphabetSorted, "");
        }


        for (HashMap<String, Integer> count : courseMap.values()) {
            count.values()
                    .stream()
                    // 가장 높은 값 찾기
                    .max(Comparator.comparing(o -> o))
                    // 방금 찾은 가장 높은값으로 비교 시작
                    .ifPresent(cnt -> count.entrySet()
                            .stream()
                            // 값이 같은지 찾고 2이상인지 체크
                            .filter(entry -> cnt.equals(entry.getValue()) && cnt > 1)
                            // 같은 값이 여러개 있어도 배열에 추가
                            .forEach(entry -> answer.add(entry.getKey())));
        }

        Collections.sort(answer);
        return answer.toArray(new String[0]);
    }

    // 문자열을 캐릭터로 잘라서 배열로 리턴
    public static String[] alphabetSort(String std) {
        return Arrays.stream(std.split("")).sorted().toArray(String[]::new);
    }

    public static void addCombinations(int idx, String[] order, String result) {

        // 초기에 course 배열에 있던 갯수만큼의 길이 인지 체크
        if (courseMap.containsKey(result.length())) {
            HashMap<String, Integer> map = courseMap.get(result.length());
            // 코스 알파벳에 해당되는 Map에 value 값 증가
            map.put(result, map.getOrDefault(result, 0) + 1);
        }

        // 각 문자열에 인덱스 별로 재귀 호출
        // 예시 "ABCDEFG" 라는 order[]가 초기 들어온다.
        // 1. "" + "A", "" + "B", "" + "C" + "" + "D" + ... 이런식으로 1번째 반복문 동작
        // 다만 bfs처럼 큐형식으로 동작하는게 아닌 dfs처럼 한번 재귀호출 타면 "" + "A"부터 끝까지 천천히 탄다.
        for (int i = idx; i < order.length; i++) {
            addCombinations(i + 1, order, result + order[i]);
        }
    }
}