메뉴 리뉴얼(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

각 order를 course에 해당하는 길이로 조합해서 개수가 가장 많은 조합을 return

 

---

 

풀이

 

문제 해석

각 order를 알파벳순으로 정렬해서 course에 해당하는 길이로 조합을 만들어 개수가 가장 많은 조합 구하기

 

 

접근 방식

1) 알바벳순으로 정렬

  → .toCharArray()를 통해 String을 char[]로 변환 후 Arrays.sort(char[])를 통해 알파벳순으로 정렬

 

2) 재귀함수를 사용해 해당 order를 가지고 조합 구하기

  → "AC"와 "CA"는 서로 같으므로 알파벳순으로 정렬 후 조합 구하기

 

3) 개수가 가장 많은 요소 구하기

  → Collections.max(map.values())를 통해 max 구해서 비교

 

---

 

코드 리뷰

 

import java.util.*;

class Solution {
    HashMap<String, Integer> map = new HashMap<>();
    
    public void recursive(String comb, String remains, int maxLength) {	// 조합 구하는 재귀함수
        if(comb.length() == maxLength) {	// 탈출조건(조합의 길이가 course의 길이와 같으면 탈출)
            map.put(comb, map.getOrDefault(comb, 0) + 1);
            return;	// void 타입의 메소드는 return을 만나면 탈출
        }
        for(int i = 0; i < remains.length(); i++) {	// 문자 하나씩 붙여서 다음 재귀함수의 첫 번째 인자로 넘김
            recursive(comb + remains.substring(i, i+1), remains.substring(i+1), maxLength);	// 두 번째 인자는 하나 뗀 나머지 문자열, 세 번째 인자는 course 길이로 고정
        }
    }
    public String[] solution(String[] orders, int[] course) {
        List<String> answerList = new ArrayList<>();
        for(int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();	// 알파벳순으로 정렬하기 위해 .toCharArray()로 변환
            Arrays.sort(arr);	// Arrays.sort()로 정렬
            String s = "";
            for(char c : arr) {
                s += String.valueOf(c);	// 다시 String으로 변환
            }
            orders[i] = s;	// 정렬된 문자열을 배열에 대입
        }
        int max = 0;
        for(int i : course) {
            for(String str : orders) {
                recursive("", str, i);	// orders의 요소들을 순회하며 course의 길이만큼 만든 조합들이 map에 담김
            }
            if(!map.isEmpty()) {	// map에 데이터가 존재하는지 확인(매우 중요!)
                max = Collections.max(map.values());	// values중 max값 구하기
            }
            for(String str : map.keySet()) {
                if(max >= 2 && map.get(str) == max) {	// max >= 2 일때만 유효
                    answerList.add(str);
                }
            }
            map.clear();	// course의 길이가 바뀌기 전 이전 길이로 채워진 map 비우기
        }			// claer를 안하면 이전에 담긴 value들이 max 찾을 때 영향을 끼침
        Collections.sort(answerList);	// 알파벳순으로 정렬해서 return
        String[] answer = new String[answerList.size()];
        for(int i = 0; i < answer.length; i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }
}

 

 

 

* refs

https://www.youtube.com/watch?v=Jb34jY91450&list=PLlV7zJmoG4XI9VguUVNMu3pCjssb4aR_0&index=8