[프로그래머스] 메뉴 리뉴얼(java)

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

프로그래머스

조합을 이용한 문제이다.

 

 

핵심

사람들이 주문한 상품들을 갖고 조합을 만들어서 가장 많이 나온 조합으로 메뉴를 만드는 것이다.

로직 자체는 있는 단순하다.

 

 

정답 코드

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

class Solution {
    static Map<String, Integer> orderCount;
    static int max;
    static List<String> results;
    public String[] solution(String[] orders, int[] course) {
        results = new ArrayList<>();
        for (int cutSize : course){
            max = 0;
            orderCount = new HashMap<>();
            for (String s : orders){
                comb(s,"",0, cutSize);
            }
            if (max<2)continue;
            orderCount.entrySet().stream().filter(e -> e.getValue() == max)
                    .forEach(e -> results.add(e.getKey()));
        }
        Collections.sort(results);
        return results.toArray(new String[0]);
    }

    public void comb(String word, String now, int index ,int cutSize){
        if (now.length() == cutSize){
            String sortedWord = sort(now);
            orderCount.put(sortedWord, orderCount.getOrDefault(sortedWord,0)+1);
            max = Math.max(max, orderCount.get(sortedWord));
            return;
        }

        for (int i = index; i < word.length(); i++){
            comb(word,now+word.charAt(i), i+1,cutSize);
        }
    }

    public String sort(String word){
        return Arrays.stream(word.split("")).sorted().collect(Collectors.joining());
    }
}

해설

우선 세트 메뉴의 개수 별로 조합을 달리해야 한다. 따라서 course의 길이만큼 반복문을 실행하며

그때의 길이로 조합을 만든다.

comb메서드 조합은 ex) abc , 길이가 2->  ab, ac, bc가 나올 수 있도록 설계하였다.

중요한 점은 이렇게 탐색하면 만약 어떠한 메뉴의 위치에 따라 WX, XW 이런 식으로 같은 상품이지만 순서가 달라서

다른 메뉴로 취급하게 된다. 따라서 정렬을 해야 한다.

이런 식으로 조합을 이루면 

위와 같은 모양으로 map에 담기게 된다.

또한 길이별로 최대 값을 저장하고, 그때 그 최댓값과 같은 value를 가진 key값을 result에 담는다.

또한 max값이 2 이상이 아니면 무시하고 진행한다.

 

 

배운 점

아이디어 자체는 매우 쉽고 빠르게 생각해 냈다. 하지만 조합을 만드는 과정에서 index 위치에 i+1을 넣어야 하는데,

처음에 index+1을 넣어서 오랜 시간 삽질을 하였다. 이러한 실수를 하지 않도록 꼼꼼하게 문제를 푸는 습관을 길러야겠다.

또한 문제의 조건인 주문이 2건 이상만 포함이란 조건도 처음에 캐치하지 못하였다.

문제를 빠르게 푸는 것도 중요하지만 정확하게 푸는 습관을 들이자.