[JAVA] 2021 카카오문제 - 메뉴 리뉴얼

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

코딩테스트 연습 - 메뉴 리뉴얼

 

💡 개요

 

문제는 보고 오셨다고 생각하고 바로 풀이 하겠습니다.

 

dfs 재귀를 통한 완전탐색 하셔도 되지만 저는 비트마스킹을 통한 완전탐색을 선택했습니다. 그 이유는 단어의 특징때문입니다.

하나의 주문에 들어가는 메뉴는 중복되는 알파벳이 없다는 점 때문입니다.

 

알파벳은 아래처럼 각각 하나의 숫자에 대응됩니다.

 

'A' - 1

'B' - 1<<1

'C' - 1<<2

'D' - 1<<3

'E' - 1<<4

...

'Z' - 1<<26

 

<< 기호는 Shift 연산자입니다. 

 

이러한 알파벳이 모여서 하나의 숫자가 됩니다.

예를 들어, 'ABC' - > 1 + 1<<2 + 1<<3 = 111(2) 가 되고 10진법으로 표현하면 7 입니다.

 

💡 문제 접근 법

1. 모든 주문(단어)들에 대해서 숫자 단어를 만듭니다. orders를 받아서 각각의 String 을 char[] 로 변환한 뒤 words 라는 int 배열에 담아줍니다.

public void makeWords(String[] orders) {
        int idx = 0;
        for(String o : orders) {
            int n = 0;
            for(char c : o.toCharArray()) n += 1<<(c-'A');
            words[idx++] = n;
        }
 }

2. 알파벳 26개 중에서 c 에 해당하는 숫자 만큼 선택하는 경우를 탐색합니다. 이부분은 비트마스킹을 통한 완전탐색 개념이 생소하시면 이해하기 힘들 수 잇습니다. 만약 c = 3 이라면 26개 알파벳 중에서 3개를 뽑아야 합니다.  1부터 1<<26까지 1씩 증가하면서 비트의 수가 3개라면 3개 선택된 것이라고 볼 수 있으므로 해당 숫자가 바로 result 에 들어갈 문자열입니다. 에를 들어, 10011 (2) 이라는 숫자가 있다고 가정해봅시다.  그러면 'ABE' 를 선택한 경우를 말하고 'ABE' 가 result 에 들어가도 되는지 검사후 result에 추가하게 됩니다. 

for(int c : course) {
            for(int i=1;i<1<<26;i++) {
                if(Integer.bitCount(i) == c) {
                    int mask = i;
                    int cnt = 0;
                    for(int w : words) if ((mask & w) == mask) cnt++;
                    if(cnt < 2) continue;
                    if(courseMax[c] <= cnt) {
                        if(courseMax[c] < cnt) courseList[c] = new ArrayList();
                        courseMax[c] = cnt;
                        courseList[c].add(mask);
                    }
                }
            }
        }

3. 숫자들의 리스트들의 리스트를 문자열 배열로 바꾸는 과정이 필요합니다. 

public String[] makeAns() {
        List<String> ret = new ArrayList<>();
        for(List<Integer> l : courseList) for(int i : l) ret.add(makeString(i));
        Collections.sort(ret, String::compareTo);
        return ret.toArray(new String[0]);
    }
    
    public String makeString(int a) {
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        for(int i=1;i<1<<26;i<<=1) {
            if((a&i)>0) sb.append((char)('A'+idx));
            idx++;
        }
        return sb.toString();
    }

 

💪 전체 코드

package programers.kakao2021.메뉴리뉴얼;
import java.util.*;

public class Solution {
    static int[] words = new int[20];
    static int[] courseMax = new int[11];
    static List<Integer>[] courseList = new ArrayList[11];

    public String[] solution(String[] orders, int[] course) {
        for(int i=0;i<11;i++) courseList[i] = new ArrayList<>();
        makeWords(orders);
        for(int c : course) {
            for(int i=1;i<1<<26;i++) {
                if(Integer.bitCount(i) == c) {
                    int mask = i;
                    int cnt = 0;
                    for(int w : words) if ((mask & w) == mask) cnt++;
                    if(cnt < 2) continue;
                    if(courseMax[c] <= cnt) {
                        if(courseMax[c] < cnt) courseList[c] = new ArrayList();
                        courseMax[c] = cnt;
                        courseList[c].add(mask);
                    }
                }
            }
        }
        return makeAns();
    }

    public String[] makeAns() {
        List<String> ret = new ArrayList<>();
        for(List<Integer> l : courseList) for(int i : l) ret.add(makeString(i));
        Collections.sort(ret, String::compareTo);
        return ret.toArray(new String[0]);
    }

    public String makeString(int a) {
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        for(int i=1;i<1<<26;i<<=1) {
            if((a&i)>0) sb.append((char)('A'+idx));
            idx++;
        }
        return sb.toString();
    }

    public void makeWords(String[] orders) {
        int idx = 0;
        for(String o : orders) {
            int n = 0;
            for(char c : o.toCharArray()) n += 1<<(c-'A');
            words[idx++] = n;
        }
    }

    public static void main(String[] args) {
        for(String s : new Solution().solution(new String[]{
                "ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"
        },new int[]{2,3,4})){
            System.out.println(s);
        }
    }

}