[프로그래머스][JAVA] 메뉴 리뉴얼 (조합, 백트래킹)

2022. 3. 18. 16:32· 알고리즘 풀이/프로그래머스
728x90

1. orders배열의 order들을 toCharArray()로 char[]로 변환 후 Arrays.sort(char[]) 후에 String.valueOf(char[])로

알파벳 순으로 정렬된 주문 요리순서로 바꿈

(이거 안해주면 나중에 map으로 누적시킬 때 "XY" "YX" 이런 요리 조합이 따로 누적됨)

 

2. comb 메서드는 계속 하면 indexOutOfRange뜨다가 결국 완성함

 

3. combOrder 메소드의 마지막 parameter인 int PreIdx가 핵심이었는데 이걸 안해주면

XYZ의 조합에서 ZZZ

AB 조합에서 BB

이런 것이 나옴

 

4. mostOrderNum int[]을 통해 n개 조합의 최다 주문된 횟수를 mostOrderNum[n]에 Math.max를 통해 계속 갱신시켜줄것

 

 

import java.util.*;

class Solution {
    private static Map<String, Integer> menuMap;
    private static int[] mostOrderNum; // 코스요리 중 가장 많이 주문된 횟수 (index는 코스요리 조합 수임)
    
    public String[] solution(String[] orders, int[] course) {
        menuMap = new HashMap<>();
        mostOrderNum = new int[11];

        
        for(String order : orders){
            // System.out.println(order);
            char[] chArr = order.toCharArray();
            Arrays.sort(chArr);
            order = String.valueOf(chArr);
            // System.out.println(order);
            
            analyzeCourseMenu(order);
        }
        
        List<String> resultList = new ArrayList<>();
        
        for(Map.Entry<String,Integer> e : menuMap.entrySet()){
            String finalMenu = e.getKey();
            int finalMenuAccum = e.getValue();
            // System.out.println(e.getValue()+" "+e.getKey());
            
            for(int c : course){
            // 코스요리 메뉴의 주문 횟수가 2회 이상이고, c개의 요리들의 조합이고, 주문횟수가 c개 요리들 중 최다주문 횟수와 일치
                if(finalMenuAccum>=2 && finalMenu.length()==c && finalMenuAccum==mostOrderNum[c]){
                    resultList.add(finalMenu);
                }
            }
        }
        Collections.sort(resultList);
        // resultList.forEach(System.out::println);
        
        String[] answer = new String[resultList.size()];
        for(int i=0; i<resultList.size(); i++){
            answer[i] = resultList.get(i);
        }
        
        return answer;
    }
    
    private void analyzeCourseMenu(String order){
        for(int combNum=2; combNum<=order.length(); combNum++){
            
            // visited 데이터는 필요 없는듯..
            // boolean[] visited = new boolean[order.length()];
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<order.length(); i++){
                sb.append(order.charAt(i));
                // visited[i] = true;
                
                combOrder(order, sb, combNum, 1, i);
                
                sb.deleteCharAt(sb.length()-1);
                // visited[i] = false;
            }

        }
    }
    
    private void combOrder(String order, StringBuilder sb, int combNum, int preNum, int preIdx){
        if(preNum==combNum){
            // System.out.println((preNum)+" "+sb.toString());
            String finalMenu = sb.toString();
            int finalMenuAccum = menuMap.getOrDefault(finalMenu, 0)+1;
            menuMap.put(finalMenu, finalMenuAccum);
            mostOrderNum[preNum] = Math.max(mostOrderNum[preNum], finalMenuAccum);
            
            return;
        }
        for(int i=preIdx+1; i<order.length(); i++){
            // if(visited[i]) continue;
            sb.append(order.charAt(i));
            // visited[i] = true;
            
            combOrder(order, sb, combNum, preNum+1, i);
            sb.deleteCharAt(sb.length()-1);
            // visited[i] = false;
            
        }
        
    }
        
//     private class MenuComb{
//         String menuComb;
//         int accum;
        
//         public MenuComb(String menuComb, int accum){
//             this.menuComb = menuComb;
//             this.accum = accum;
//         }   
//     }
}​
저작자표시 (새창열림)

'알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글

[프로그래머스][JAVA] [1차] 뉴스 클러스터링 (문자열)  (0) 2022.03.19
[프로그래머스][JAVA] 괄호 변환 (재귀, 문자열)  (0) 2022.03.19
[프로그래머스][JAVA] 행렬 테두리 회전하기 (구현)  (0) 2022.03.18
[프로그래머스][JAVA] 짝 지어 제거하기 (스택)  (0) 2022.03.17
[프로그래머스][JAVA] 타겟넘버 (DFS)  (0) 2022.03.17
'알고리즘 풀이/프로그래머스' 카테고리의 다른 글
  • [프로그래머스][JAVA] [1차] 뉴스 클러스터링 (문자열)
  • [프로그래머스][JAVA] 괄호 변환 (재귀, 문자열)
  • [프로그래머스][JAVA] 행렬 테두리 회전하기 (구현)
  • [프로그래머스][JAVA] 짝 지어 제거하기 (스택)
배게
배게
배게
백엔드
배게
전체
오늘
어제
  • 분류 전체보기 (430)
    • 알고리즘 풀이 (338)
      • 백준 (167)
      • Codility (22)
      • 프로그래머스 (123)
      • LeetCode (2)
      • CodeForces (9)
      • SWEA (15)
    • 백엔드 (11)
    • Coding existing for (3)
    • 무지성 메모 (40)
    • Debug (30)
    • 자바 (8)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • MYSQL
  • hibernate
  • 카카오톡 txt파일 정렬
  • 카톡 내보내기한 파일 정렬
  • 카톡
  • 카카오톡

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
배게
[프로그래머스][JAVA] 메뉴 리뉴얼 (조합, 백트래킹)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.