문제 URL : https://programmers.co.kr/learn/courses/30/lessons/72411
코딩테스트 연습 - 메뉴 리뉴얼
레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서
programmers.co.kr
문제 접근법 :
orders의 모든문자열의 부분집합들을 구해서 그부분집합들의 개수를 count해주는겁니다. 무슨뜻이냐면
첫뻔째 테스트케이스에 ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
ACDE의 모든 부분집합은
길이가 1일때 : A,C,D,E
길이가 2일때 :AC,AD,AE,CD,CE,DE
길이가 3인것 :ACD,ACE,ADE,CDE
길이가 4인것 :ACDE
총 15개가 나오며 A는 A의 개수가 몇개인지 카운팅하며
AC는 AC가 몇개인지 카운팅하며 ACD, ACDE 카운팅합니다. 이모든것을 orders의 모든 문자열의 부분집합을 구하면서 카운팅 한다음 해당길이가 course 안에 포함된것중에 가장 카운팅이 높은녀석을 answer에 담아줘야합니다.
하지만 이문자열을 전부 부분집합을 구하는 연산은 꽤 느리기때문에
저는비트마스크를이용했고 orders의 문자열을 전부 비트마스크화 시키면 그 부분집합도 for문으로 쉽게 구할수있습니다.
소스코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <bits/stdc++.h>
using namespace std;
int bitcount(int n) {
if (n == 0)return 0;
return n % 2 + bitcount(n / 2);
}
vector<string> solution(vector<string> orders, vector<int> course) {
vector<string> answer;
vector<int> res[11];
int rescnt[11] = { 0 };
int bitlength[11] = { 0 };
map<int, int> set;
//course요리에 포함되는지 미리 알기위해
for (int i = 0; i < course.size(); i++) {
bitlength[course[i]] = 1;
}
vector<int> order(orders.size(), 0);
//orders를 order안에 비트마스크화 시킴
for (int i = 0; i < orders.size(); i++) {
for (char c : orders[i]) {
order[i] |= (1 << (c - 'A'));
}
}
//order의 모든 부분집합을 카운팅
for (int i = 0; i < order.size(); i++) {
for (int subset = order[i]; subset; subset = ((subset-1)&order[i])) {
set[subset]++;
}
}
for (auto it : set) {
//주문한것이 2보다 작으면 볼필요없음
if (it.second < 2)continue;
int bit = bitcount(it.first);//bitcount 자체가 order의 부분집합의 길이를 뜻함
if (!bitlength[bit])continue;
if (rescnt[bit] < it.second) {
res[bit].clear();
res[bit].push_back(it.first);
rescnt[bit] = it.second;
}
else if (rescnt[bit] == it.second) {
res[bit].push_back(it.first);
}
}
//비트마스크화 시킨것을 다시 문자열로 바꿈
for (int i = 0; i < course.size(); i++) {
for (int words : res[course[i]]) {
string s;
int idx = 0;
while (words) {
if (words % 2)s += ('A' + idx);
words /= 2;
idx++;
}
answer.push_back(s);
}
}
sort(answer.begin(), answer.end());
return answer;
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 수식 최대화 (2020 카카오 인턴십) (0) | 2021.08.02 |
|---|---|
| 프로그래머스 문자열 압축(2020 KAKAO BLIND RECRUITMENT) (0) | 2021.08.01 |
| 프로그래머스 괄호 변환 (2020 KAKAO BLIND RECRUITMENT) (1) | 2021.07.31 |
| 프로그래머스 신규 아이디 추천(2021 KAKAO BLIND RECRUITMENT) (0) | 2021.07.31 |
| 프로그래머스 삼각 달팽이 (0) | 2021.07.31 |
