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

 

for(int i = 0; i < others.length(); i++) {
    // i번째 까지는 조합을 했으므로, i+1부터는 사용되지 않은 알파벳
    dfs(order + others.charAt(i), others.substring(i+1), count - 1);
}

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

프로그래머스

문제 풀이 접근

1. 맨 처음에 주어진 각 order를 정렬하자. (AW, WA는 같은 값이여야 한다)

2. 각 order를 기준으로 courseLength ex) 2,3,4.. 만큼 조합을 만들자

3. 가장 많이 등장한 조합을 answer에 저장하자

3-1. 해쉬맵의 value값들을 리스트에 담고, max 값을 찾는다.

3-2. 해쉬맵을 순회하면서 value값과 max값이 동일하다면, 우리가 찾는 메뉴이므로 answer에 저장한다.

4. 리스트 형태를 배열로 바꿔준다.

import java.util.*;
class Solution {
    static Map<String,Integer> map = new HashMap<>();
    static List<String> answerList = new ArrayList<>();
    public String[] solution(String[] orders, int[] course) {   
        
        // 1. 각 order 정렬
        for(int i = 0; i < orders.length; i++) {
            char [] chars = orders[i].toCharArray();
            Arrays.sort(chars);
            orders[i] = String.valueOf(chars);
        }
        
        // 2. 각 order를 기준으로 courseLength 만큼 조합 만들기
        for(int courseLength : course) {
            for (String order : orders) {
                dfs("", order, courseLength);
            }
            
            // 3. 가장 많은 조합을 answer에 저장
            
            if (!map.isEmpty()) {
                // 4. 해쉬맵의 value를 리스트에 담고 max값을 찾는다.
                List<Integer> countList = new ArrayList<>(map.values());
                int max = Collections.max(countList);
                
                if (max > 1) {
                    for(String key : map.keySet()) {
                        if (map.get(key) == max) {
                            answerList.add(key);
                        }
                    }
                }
                map.clear();
            }
        }
        
        Collections.sort(answerList);
        String [] answer = new String[answerList.size()];
        
        for(int i = 0; i < answer.length; i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }
    
    // order - 현재까지 조합된 course
    // others - 사용되지 않은 알파벳
    // count - 몇 개를 조합해야 하는지
    private void dfs(String order, String others, int count) {
        
        if (count == 0) {
            map.put(order, map.getOrDefault(order, 0) + 1);
            return;
        }
        
        for(int i = 0; i < others.length(); i++) {
            // i번째 까지는 조합을 했으므로, i+1부터는 사용되지 않은 알파벳
            dfs(order + others.charAt(i), others.substring(i+1), count - 1);
        }
    }
}

 

문제 풀이 회고

 

1. 조합을 만들 땐 정렬을 고려하자.
2. HashMap의 기본 형태는 name:count
3. 재귀 = 탈출 조건 + 수행 동작

여러가지 개념이 쓰였던 문제였는데, 처음엔 감이 오지 않다가 유투브 영상을 보니 완벽하게 이해가 됐다.

https://www.youtube.com/watch?v=Jb34jY91450

 

for(int i = 0; i < others.length(); i++) {
    // i번째 까지는 조합을 했으므로, i+1부터는 사용되지 않은 알파벳
    dfs(order + others.charAt(i), others.substring(i+1), count - 1);
}

개인적으로 substring을 사용하여 사용되지 않은 부분을 추적하는게 직관적으로 와닿지가 않았는데,

 

private void dfs(String order, int depth, String others, int count, boolean [] visited) {
        
    if (count == 0) {
        map.put(order, map.getOrDefault(order, 0) + 1);
        return;
    }

    for (int i = depth; i < others.length(); i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(order + others.charAt(i), i+1, others, count - 1, visited);
            visited[i] = false;
        }
    }
}

 

visited 배열을 만들어서 각 order마다 초기화를 해주고, depth를 추가해서 시작점을 depth로 설정해주는 방법으로 해결해도 된다.

 

이 문제는 무조건 다시 한번 풀어봐야겠다. 재귀 + 백트래킹 + 맵이 섞인 문제가 나오니까 처음에 많이 힘들었다