2021 KAKO BLIND RECRUITMENT [메뉴리뉴얼] [C++]

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

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

---

문제요약

1.orders 배열에 idx번째 사람이 주문한 음식이 문자열로 주어지고

2.코스요리를 구성하는 단품메뉴들의 갯수가 담긴 course 배열이 주어질때

3.가능한 세트구성을 문자열을 배열에 담아 반환한다.

<단 세트를 구성할때는 최소 2명이상의 손님으로 부터 주문된 단품메뉴 조합에 대해서만 후보에 포함한다>

 

 

---

나의 풀이

일단 문제부터 잘 이해가 되지 않았다. 

입출력 예에 대한 설명을 보고 나서야 이해가 갔다.

 

만약 1,2,3번 손님이 "ABCD" "BCDE" "CE" 이렇게 주문을 하였고 course 가 [2] 였을 경우

"2개의 단품메뉴를 셋트메뉴로 만들어야하고 해당2개의 메뉴는 최소 2명에게 동시에 선택되어야 한다"

 

예를 들어 "BC"는 1,2 번 손님에게 주문되었지만

"CE"에 대해서는 2번손님에게만 주문이되었다고 생각해야된다

("C" 가 1,2,3번에 있고 "E"가 2,3번에 있으므로 된다고 생각했었다....)

 

정신을 차려 문제를 바로 깨닳고 알파벳의 index는 0(A) ~ 23(Z) 까지 이고 사람이 최대 10명이니

손님 번호주문한 단품메뉴 조합

1번 손님	A, B, C, F, G
2번 손님	A, C

이러한 데이터를 

	A	B	C	F	G
1번 손님	1	1	1	1	1
2번 손님	1	0	1	0	0

이런식으로 비트마스크로 표현하였다

A:11 B:10 C:11 F:10 G:10

---

풀이과정 

1.비트마스킹으로 사람들의 주문한 단품메뉴를 표현 (solution 함수 전처리과정)

2.order[i]에 대해서  메뉴조합을 백트래킹으로 돌려서 가능한 모든경우탐색(go 함수)

3.해당 메뉴조합의 비트들을 &연산을 통하여 최종적으로 1비트가 2개이상이라면 가능한 경우로 판별

( excute , getSelectedMenu )

---

코드