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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

이 문제는 전체적인 로직의 흐름은 어렵지 않은 편이다.

하지만 그 각각의 로직을 구현하는 방법을 모른다면 어려운 문제이다.

 

이 문제의 로직의 흐름은 다음과 같다.

 

1. 메뉴 조합별로 몇번씩 주문됐는지 파악한다.

 

2. 1의 결과를 가지고 조합의 크기별로 가장 많이 주문된 조합을 뽑아낸다.

 

3. 2에서 뽑아낸 조합들을 합쳐서 알파벳순으로 정렬한다.

 

 

언뜻보면 별거 없어보이는 문제이다.

하지만 1번을 구현하는 과정이 꽤 어려웠던 것 같다.

1번의 구현방향은 다음과 같다. 

 

1. 메뉴 조합별로 몇번씩 주문됐는지 파악한다.

 

1) orders[]를 보고 나올 수 있는 메뉴 중 크기가 course[]의 원소인 조합을 모두 뽑아낸다. 

 

 

2) 1)에서 뽑아낸 조합을 가지고 해시맵에 조합 - 주문 횟수 관계로 저장한다.

 

 

특히 1) 과정이 어려웠다. 저 부분을 구현하는데만 1시간이 걸린 것 같다.

1)은 재귀를 통해 해결해야 한다.

하지만 재귀를 구현하는 것이 생각보다 어려웠다. 

사실 재귀를 통해 모든 조합을 뽑아내는 코드는 한번 구현해본 사람이라면 쉽게 구현할 수 있는 부분일 것이다.

하지만 나는 해본적이 없었기 때문에 어려웠다.

 

바로 코드를 보도록하자.

3. 내 코드

---

import java.util.*;
class Solution {
    
    List<String> course_combs = new ArrayList<>();
    String course_comb = "";
    
    public String[] solution(String[] orders, int[] course) {
        
        HashMap<String, Integer> comb_cnt = new HashMap<>();
        List<String> answer = new ArrayList<>();
        
        // 1. 메뉴 조합별로 몇 번씩 주문 됐는지 (조합의 크기는 course[]에 의거)
        for(String order: orders) {
            order = sortString(order);
            for(int course_size: course) {
                course_combs.clear();
                course_comb = "";
                getCombination(order, course_size);
                for(String c: course_combs) {
                    comb_cnt.put(c, comb_cnt.getOrDefault(c, 0) + 1);
                }
            }
        }
        
        // 2. 1의 결과를 가지고 각 course의 크기 별로 가장 주문이 많은 코스 조합 뽑아내기
        for(int course_size: course) {
            int max_order = 2; // 최소 2번 이상 주문되어야 코스로 선정 가능
            
            // 해당 course 크기내 최다 주문 수 알아내기 
            for(String comb: comb_cnt.keySet()) {
                if(comb.length() == course_size) {
                    if(comb_cnt.get(comb) > max_order) {
                        max_order = comb_cnt.get(comb);
                    }
                }
            }
            // 가장 주문이 많았던 course 조합 뽑아내기 
            for(String comb: comb_cnt.keySet()) {
                if(comb_cnt.get(comb) == max_order && comb.length() == course_size) {
                    answer.add(comb);
                }
            }
        }
        
        
        // 3. 2의 결과 오름차순으로 정렬하기
        Collections.sort(answer);
        
        return answer.toArray(new String[0]);
    }

    void getCombination(String order, int course_size) {
        
        if(course_size == 0) {
            course_combs.add(course_comb);
            return;
        }
        
        course_size--;
        for(int i = 0; i < order.length(); i++) {
            course_comb += order.substring(i, i + 1);
            getCombination(order.substring(i + 1), course_size);
            course_comb = course_comb.substring(0, course_comb.length() - 1);
        }
        
    }
    
    String sortString(String s) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        return String.valueOf(arr);
    }
}

시간 복잡도

• O(n * m^c * c^2)
• n: orders 배열의 길이
• m: orders원소의 최대 길이 
• c: course 배열의 최댓값

 

4. 피드백

---

• 문자열이나 배열에서 나올 수 있는 모든 조합을 뽑아내려면 재귀 알고리즘을 통해 풀어야 한다.

추가

• 문자열 알파벳순으로 정렬하는 코드

String sortString(String s) {
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    return String.valueOf(arr);
}