[Programmers] 메뉴 리뉴얼 (Lv.2) 2023/7/12

문제 제목	정답률	난이도
메뉴리뉴얼	48%	Lv.2

프로그래머스

 

문제요약

손님번호와 손님이 주문한 단품메뉴 조합이 주어질 때, 새로운 코스 요리를 구하여라.

조건 1) 새로운 코스요리는 단품메뉴 2개 이상으로 구성되어야 한다

조건 2) 새로운 코스요리는 손님이 주문한 단품메뉴 조합에 적어도 2번 이상 포함되어야 한다(손님이 2번 이상 주문)

조건 3) 정답 배열은 문자열 오름차순으로 정렬되어 반환되어야 한다.

조건 4) 코스 요리의 단품메뉴 개수가 같을 경우, 더 많이 주문된 것을 메뉴에 추가한다(같다면 둘 다 추가)

조건 4의 경우 문제에 기술되어 있지는 않지만, 질문하기 게시판을 통해 알 수 있었다. 

 

 

생각할 것

우선, 배열의 크기와 문자열의 크기를 보고 완전 탐색이 가능한 문제인지 확인하여야 한다.

배열 길이 20, 문자열 길이 10이하로, 완전 탐색이 가능하다.

 

풀이

Step1. course 값에 대해서 모든 경우의 수 찾기 String[] dfs(String str, int len){return String[]} 함수

• stack 길이==현재 course ⇒ 경우의 수 추가 + pop()
• stack 길이==0 ⇒ push
• 나머지[1~course-1] ⇒ 기본적으로 push하되, 남은 원소가 없으면 pop()

 

Step2. 해당 경우를 hashmap 이용하여 dictionary 형태로 저장("요리목록":주문개수)

 

Step3. dictionary로 저장할 때 각 course 값에 대해 maxValue를 업데이트하여, maxValue에 해당하는 dictionary만 정답에 추가

 

Step4. 정답 형태를 정렬한 뒤, array로 변환

 

 

코드

import java.util.*;
class Solution {
    String[] dfs(String str, int len){
        List<String> vector=new ArrayList<String>();
        int[] idx_stack=new int[len];
        int top=-1;
        int start_idx=-1;
        int last_idx=0;
        while(start_idx<=str.length()-len){
            if(top==-1){//push
                idx_stack[++top]=++start_idx;
                last_idx=start_idx;
            }else if(top==(len-1)){//최대 원소 채움
                String nowstr="";
                for(int idx:idx_stack){
                    nowstr+=str.substring(idx, idx+1);
                }
                vector.add(nowstr);

                last_idx=idx_stack[top--];
                while(top>-1){
                    if(last_idx+1<=(str.length()-1)){//현재 원소 len-1개
                        break;
                    }else{//현재 원소 len-2개->pop
                        last_idx=idx_stack[top--];
                    }
                }
            }else{//1개 이상 최대-1 이하
                while(top>-1){
                    if(last_idx+1<=(str.length()-1)){//push
                        idx_stack[++top]=++last_idx;
                        break;
                    }else{//pop
                        last_idx=idx_stack[top--];
                    }
                }
            }
        }
        return vector.toArray(new String[vector.size()]);
    }
    public String[] solution(String[] orders, int[] course) {
        List<String> answer = new ArrayList<String>();
        for(int c_num:course){
            int maxCount=0;
            Map<String, Integer> ht = new HashMap<String, Integer>();
            for(int i=0; i<orders.length;i++){
                char[] str_char=orders[i].toCharArray();
                Arrays.sort(str_char);
                String now_order=new String(str_char);
                if(now_order.length()>=c_num){
                    String[] s_list=dfs(now_order, c_num);
                    for(String substr:s_list){
                        if(ht.containsKey(substr)==true){
                            ht.put(substr, ht.get(substr)+1);
                            if(maxCount==1){
                                maxCount=2;
                            }else{
                                if(maxCount<ht.get(substr)){
                                    maxCount+=1;
                                }
                            }
                        }else{
                            ht.put(substr, 1);
                            if(maxCount==0){
                                maxCount=1;
                            }
                        }
                    }
                }
            }
            for(String idx:ht.keySet()){
                if(maxCount<2){
                    break;
                }
                else if(ht.get(idx)==maxCount){
                    answer.add(idx);
                }else{
                    continue;
                }
            }
        }
        answer.sort(null);
        return answer.toArray(new String[answer.size()]);
    }
}

 

사용한 기능 정리

- 문자열 substring

문자열변수.substring(시작 인덱스, 끝 인덱스+1)

 

- List 정렬

List변수.sort(null)

 

- List -> Array 변환

List변수.toArray(new 자료형(List변수.size()) 

 

- 해시 함수 사용

Map<key자료형, value자료형> 변수명 = new HashMap<key자료형, value자료형>();

• 값 추가     변수명.put(key, value)
• 값으로 삭제    변수명.values().remove(삭제할값)
• 조건으로 삭제    변수명.values().removeIf(조건)
• 모든 키 가져오기    변수명.keySet()
• 모든 값 가져오기    변수명.values()
• 키값이 존재하는지 확인    변수명.containsKey(키값)

 

 

한 줄 정리

해당 내용은 python의 dictionary 자료형을 사용하면 상당히 빠른 시간 내에 풀 수 있었다.

Java 자료형 변환이 아직 익숙하지 않아서 시간이 많이 걸린 문제!