문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/72411
2021 카카오 블라인드 코딩 테스트에서 나온 문제.
자료구조 Map을 잘 알아야 풀 수 있는 문제 같다.
Map을 사용하지 않고 다른 건 잘 모르겠다.
문제 핵심 및 풀이
메뉴(orders)의 개수가 최대 20개,
메뉴 조합(course)의 가짓수는 최대 10가지.
문제 풀이에 핵심이 되는 조합과 개수가 엄청 작기 때문에,
해당 문제는 완전 탐색으로 풀 수 있다.
여기서 문제가 되는 것은 메뉴 조합이 구성되는 방식이
"AB", "ABC" , "CDE", "A"
이렇게 정수가 아닌 문자열이기 때문에,
인덱스로 문자열을 사용하기 위해 자료구조 Map을 사용해야 한다.
orders에서 가능한 메뉴 조합
우리가 구해야 하는 것은 course가 주어졌을 때,
전체 메뉴 중에서 course에서 가장 많이 나올 수 있는 조합을 구하는 것
따라서 각 order 별로 나올 수 있는 모든 조합을 구해야 한다.
이는 백트래킹으로 모든 조합을 구한다.
여기서 핵심은 order가 만약 "ABCD"일 때,
"AA" 등 동일한 단일 메뉴가 중복되면 안 된다.
또한, "AC" 나 "CA"나 같은 구성이다.
조합을 구해줄 때 순서는 상관없다.
따라서, 백트래킹을 돌릴 때 중복을 허용하지 않는 조합을 구해야 한다.
이 점을 유의하면서 구해야 한다.
메뉴 조합별 Map을 구성한 방식
이 문제는 course 별로 나올 수 있는 최대 개수를 따로 구해줘야 한다.
그래서 Map을 course별로 나눠서 Map 배열을 만들어준다.
예를 들어 Map [2]는 메뉴 조합이 2개일 때 나올 수 있는 모든 경우의 수를 뜻한다.
실수하기 쉬운 부분
orders의 정렬
orders가 주어질 때, 해당 orders들은 정렬되어 있지 않다.
orders로 "CAB"와 "BA" 이런 식으로 주어질 수 있다.
이 상태로 백트래킹을 돌리면 Map의 key로 들어갈 인덱스가
사실상 같은 건데 다른 걸로 인식될 수 있다.
위에서는 "AB"와 "BA"가 다른 걸로 인식되어 카운트될 수 있다.
그래서 맨 처음에 orders를 정렬해 주고 시작해야 한다.
출력 형식
출력할 때 정답 배열들을 오름차순으로 출력하라고 했기 때문에
마지막에 정답 배열을 오름차순 해주는 것을 잊지 않도록 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map<string,int> m[11];
// digit 별로 한 order에서 가능한 모든 조합을 찾음
void getOrders(string orders, int digit, int cnt, string order){
if(order.size() >= digit){
m[digit][order]++;
return;
}
for(int i = cnt+1; i < orders.size(); i++){
order.push_back(orders[i]);
getOrders(orders,digit,i,order);
order.pop_back();
}
}
vector<string> solution(vector<string> orders, vector<int> course) {
vector<string> answer;
// 순서를 위해 order을 모두 오름차순 정렬
for(auto order : orders){
for(auto digit : course){
sort(order.begin(),order.end());
getOrders(order,digit,-1,"");
}
}
// 코스 메뉴 개수 별로 가장 많은 value를 가진 것을 가져옴
for(auto digit : course){
int high = 0;
vector<string> tmp;
for(auto it : m[digit]){
// high 보다 클 경우 여태까지의 vector 초기화
if(it.second > high){
high = it.second;
tmp.clear();
tmp.push_back(it.first);
}
// 그렇지 않을 경우 추가만
else if(it.second == high) tmp.push_back(it.first);
}
if(high <= 1) continue; // 2번 이상 언급된 것만 가능
for(auto it : tmp) answer.push_back(it);
}
sort(answer.begin(),answer.end()); // 오름차순 정렬
return answer;
}↑
Java 구현 코드
↓
import java.util.*;
class Solution {
static Map<String, Integer>[] m = new HashMap[11];
// 나올 수 있는 모든 경우의 수를 구함
void getOrders(String words, int count, String order, int cnt) {
if (order.length() >= count) {
if (m[count].containsKey(order))
m[count].put(order, m[count].get(order) + 1);
else m[count].put(order, 1);
return;
}
for (int i = cnt + 1; i < words.length(); i++) {
getOrders(words, count, order + words.charAt(i), i);
}
}
public String[] solution(String[] orders, int[] course) {
List<String> ans = new ArrayList<>();
for (int i = 0; i <= 10; i++) {
m[i] = new HashMap<>();
}
// key값의 중복을 방지하기 위해 모든 orders 값을 오름차순 정렬
for (int i = 0; i < orders.length; i++) {
char[] tmp = orders[i].toCharArray();
Arrays.sort(tmp);
orders[i] = new String(tmp);
}
// 코스요리 개수 별로 가능한 모든 경우의 수를 구한다.
for (int digit : course) {
for (String order : orders) {
getOrders(order, digit, "", -1);
}
}
for (int digit : course) {
int high = 0;
List<String> tmp = new ArrayList<>();
// 코스 요리 개수 별로 모든 맵의 키로 순회
for (String key : m[digit].keySet()) {
int value = m[digit].get(key); // 해당 코스 요리가 가능한 메뉴의 수
// 해당 코스 요리 개수에서 가장 큰 것만 추출
if (value > high) {
high = value;
tmp.clear();
tmp.add(key);
} else if (value == high) tmp.add(key);
}
if (high <= 1) continue; // 해당 코스요리 메뉴 수가 2개 이상이어함
ans.addAll(tmp);
}
Collections.sort(ans); // 오름차순으로 정렬
return ans.toArray(new String[0]); // String[] 배열로 전환
}
}↑
시행착오
Map을 잘 사용하지 못해서 풀지 못했던 문제,
또한 백트래킹을 조합으로 했어야 하는 점을 인지하지 못했다.
푸는 법은 대충 알았는데, 너무 대충 알았던 것이 문제였다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me