문제 분류
- 프로그래머스 레벨 2 [ 체감은 3 정도... ]
- 완전 탐색(조합), Map 자료구조, 정렬
필요한 예상 시간
- 빠르게 파악하면 1시간. 디버그 하면서 진행하면 2시간
첫 25분의 고민과정
손님이 주문한 단품 메뉴들에서 반복해서 주문되는 단품 메뉴의 조합을 찾고 우선순위를 매기는 문제이다.
10~ 15분 정도를 고민했을 때 그렇다 할 알고리즘이 떠오르지 않았다.
막막할 때의 해결책은 모든 가능성을 탐색하는 것이다.
그리고 알고리즘에서는 이 방식을 완전 탐색이라고 부른다.
각 손님이 주문한 메뉴들에서 course로 들어온 인자들에 대해서 조합의 개수를 구하는 것이다.
그리고 그 조합들을 Map 자료구조에 넣어서 카운팅을 하는 것!
Map<String, Integer> map = new HashMap<>();
boolean[] visited;
void comb(String[] foods, boolean[] visited,int len, int start, int cnt) {
if(cnt == 0) {
addComb(foods, visited, len);
return ;
}
for(int i = start; i < len; i++) {
visited[i] = true;
comb(foods, visited, len, i + 1, cnt - 1);
visited[i] = false;
}
}
void addComb(String[] foods, boolean[] visited, int len) {
String course = "";
for(int i = 0; i < len; i++) {
if(visited[i]) {
course = course + foods[i];
}
}
if(map.containsKey(course)) {
map.put(course, map.get(course) + 1);
} else {
map.put(course, 1);
}
}완전 탐색에 활용되는 템플릿으로 위의 코드를 만들어봤다.
visited[] boolean 배열을 두어서 처리하는 기법이다. 그리고 addComb 메서드를 따로 두어서 요리의 조합에 대한 개수를 카운팅 하도록 한다.
for(String order : orders) {
for(int num : course) {
char[] strTokens = order.toCharArray();
Arrays.sort(strTokens);
String sortedOrder = new String(strTokens);
String[] foods = sortedOrder.split("");
int len = foods.length;
visited = new boolean[len];
if(len >= num) {
comb(foods, visited, len, 0, num);
}
}
}이후에는 course로 넘어온 코스들의 개수를 세면서 조합들을 구하여 Map 자료구조에 보관하는 처리를 거친다.
단품 메뉴들의 개수가 코스로 제공될 음식의 개수보다 높거나 같을 때만 완전 탐색을 진행하자.
참고로 주문으로 들어온 음식들의 경우 정렬되어서 들어오는 값들이 아니다. 이 점을 유의하고 들어온 음식들을 정렬한 뒤에 정말 탐색해야 할 값으로 넘겨야 한다.
Course 객체를 따로 두어서 정렬이 편하게끔 만든다.
List<Course> courseList = new ArrayList<>();
for(Map.Entry<String, Integer> entry : map.entrySet()) {
if(entry.getValue() >= 2) {
courseList.add(new Course(entry.getKey(), entry.getValue()));
}
}문제의 조건에서 최소 2가지 이상의 단품 메뉴로 구성하고, 2명 이상의 손님으로부터 주문된 단품 메뉴 조합에 대해서만 후보에 올리기로 했다.
- 2가지 이상의 단품 메뉴는 course의 값이 2 이상으로 들어온다는 조건이 있어서 사전 조건은 만족되지만,
- 2명 이상의 손님으로부터 주문된 단품 메뉴에 대해선 map에서 값을 꺼내면서 2보다 큰지 체크해야 한다.
여기까지 온 거면 반쯤 온 것이다. 개인적으로 완전 탐색으로 조합을 생성한 뒤 Map으로만 보관하게 한 것까지만 해도 Level 2의 난이도 끝자락에 온 게 아닌가 한다...
Course라는 객체는 메뉴의 이름과, 메뉴의 개수를 변수로 가진다. 후에 정렬 시 편리하게 처리하고자 객체로 캡슐화한 것이다. 편의상 패키지 범위로 변수에 접근하게끔 하자.
class Course {
String name;
int cnt;
Course(String name, int cnt) {
this.name = name;
this.cnt = cnt;
}
}
이후 정렬을 거쳐야 한다.
Collections.sort(courseList, new Comparator<Course>() {
@Override
public int compare(Course c1, Course c2) {
if(c2.name.length() == c1.name.length()) {
return c2.cnt - c1.cnt;
} else {
return c1.name.length() - c2.name.length();
}
}
});Comparator 객체를 넘기는 방식(전략 패턴)으로 정렬을 처리한다. 일종의 콜백 메커니즘인데 Collections 유틸리티 클래스에서 sort 메서드에서 정렬이 compare() 메서드를 활용하게 하는 것이다.
이름의 길이를 먼저 비교하는데 같은 경우 주문된 개수가 먼저 오게끔 정렬 한다.
그 외에는 코스 이름으로 정렬시킨다.
위의 정렬 과정을 거치게 되면 이름이 짧은 코스 요리 순 + 이름이 같은 경우 주문 횟수가 많은 순으로 처리된다.
이제 거의 다 왔다..
최대 주문 횟수로 후보들을 걸러야 한다.
course당 max값을 보관할 배열을 두고 course들을 순회하면서 max값과 비교한다.
max값과 같으면 후보에 추가하고, max값과 다르면 그냥 넘어간다.
처음 시작 시에는 c.cname.length() == course[idx] 로 시작하니 max[idx]를 c.cnt값으로 할당한다. 이후에는 쭉쭉 진행한다. [ 개인적으론 do while문을 써도 될 듯한 부분이라고 생각하지만... for문을 이용했다. ]
int idx = 0;
int[] max = new int[course.length];
List<Course> ansList = new ArrayList<>();
for(Course c: courseList) {
if(c.name.length() == course[idx]) {
if(c.cnt > max[idx] ) {
max[idx] = c.cnt;
ansList.add(c);
} else if(c.cnt == max[idx] ) {
ansList.add(c);
} else {
continue;
}
} else {
idx = idx + 1;
max[idx] = c.cnt;
ansList.add(c);
}
}이후에는 정렬된 값들을 하나씩 빼서 객체의 이름만 추출한 뒤 값에 추가하고, 해당 String 배열을 정렬한 뒤 반환하면 된다.
System.out.println(ansList.size());
String[] answer = new String[ansList.size()];
for(int i = 0; i < answer.length; i++) {
answer[i] = ansList.get(i).name;
}
Arrays.sort(answer);
return answer;전체 코드
import java.util.*;
class Solution {
Map<String, Integer> map = new HashMap<>();
boolean[] visited;
void comb(String[] foods, boolean[] visited,int len, int start, int cnt) {
if(cnt == 0) {
addComb(foods, visited, len);
return ;
}
for(int i = start; i < len; i++) {
visited[i] = true;
comb(foods, visited, len, i + 1, cnt - 1);
visited[i] = false;
}
}
void addComb(String[] foods, boolean[] visited, int len) {
String course = "";
for(int i = 0; i < len; i++) {
if(visited[i]) {
course = course + foods[i];
}
}
if(map.containsKey(course)) {
map.put(course, map.get(course) + 1);
} else {
map.put(course, 1);
}
}
class Course {
String name;
int cnt;
Course(String name, int cnt) {
this.name = name;
this.cnt = cnt;
}
}
public String[] solution(String[] orders, int[] course) {
// System.out.println(map);
for(String order : orders) {
for(int num : course) {
char[] strTokens = order.toCharArray();
Arrays.sort(strTokens);
String sortedOrder = new String(strTokens);
String[] foods = sortedOrder.split("");
int len = foods.length;
visited = new boolean[len];
if(len >= num) {
comb(foods, visited, len, 0, num);
}
}
}
List<Course> courseList = new ArrayList<>();
for(Map.Entry<String, Integer> entry : map.entrySet()) {
if(entry.getValue() >= 2) {
courseList.add(new Course(entry.getKey(), entry.getValue()));
}
}
Collections.sort(courseList, new Comparator<Course>() {
@Override
public int compare(Course c1, Course c2) {
if(c2.name.length() == c1.name.length()) {
return c2.cnt - c1.cnt;
} else {
return c1.name.length() - c2.name.length();
}
}
});
// courseList.stream().forEach(c -> System.out.println("course " + c.name + " cnt " + c.cnt));
int idx = 0;
int[] max = new int[course.length];
List<Course> ansList = new ArrayList<>();
for(Course c: courseList) {
if(c.name.length() == course[idx]) {
if(c.cnt > max[idx] ) {
max[idx] = c.cnt;
ansList.add(c);
} else if(c.cnt == max[idx] ) {
ansList.add(c);
} else {
continue;
}
} else {
idx = idx + 1;
max[idx] = c.cnt;
ansList.add(c);
}
}
// ansList.stream().forEach(c -> System.out.println("course " + c.name + " cnt " + c.cnt));
System.out.println(ansList.size());
String[] answer = new String[ansList.size()];
for(int i = 0; i < answer.length; i++) {
answer[i] = ansList.get(i).name;
}
Arrays.sort(answer);
return answer;
}
}3개의 모듈로 분해하기
프로그래머스 Level2이지만 Level2에서도 다양한 난이도의 문제들이 공존한다.
개인적으로 카카오의 코딩 테스트 라벨이 붙은 문제들의 경우 Level3 직전에 가는 문제들이 아닌가 한다.
개인적으로 카카오의 Level2 문제를 접근하려면 완전 탐색의 패턴을 볼 수 있어야 하고, 순열이나 조합을 구현할 수 있어야 한다고 생각한다.
해당 문제도 어느 정도의 패턴이 존재하는데.
완전 탐색으로 경우의 수 구하기 -> 필요한 조건에 맞게 정렬하기 -> 정답으로 정제하기.
그리고 이 과정에서는 문제에서 드러나지 않는 여러 가지 제약사항들을 마주하게 된다.
[ 나의 경우 주문한 단품 메뉴들을 정렬하는 것이 그랬다.. ]
2시간 정도 끙끙대면서 푼 문제이다.
실제 현실 도메인에서 해결해야 할 문제이기도 할 것 같아서 재밌게 푼 문제이다.
해당 문제의 경우 완전 탐색 + 자료구조들(Map, List, Set 등등)에 대해서 능숙해야 하는 조건이 필요해 보인다.
후기
이런 문제를 코테에서 만나면 맨붕에 빠질지도 모르겠다.
프로그래머스에서 느긋하게 녹차 마시면서 푼 문제인데 긴장되는 상황이었으면 얼마나 더 끙끙 대면서 풀었을지 상상이 가질 않는다.
해당 문제는 카카오 코딩 테스트에서 3~5번쯤에 위치하지 않을까 하는 문제..
5, 6, 7은 좀 더 어려운 알고리즘 테크닉들이 요구된다.
시간이 갈수록 알고리즘 테스트 난이도의 상향 평준화가 일어나는 것 같아서 무섭기도 하다.
또한 문제 해법이 잘 보이지 않을 때는 완전탐색으로 접근해야 한다는... 경험치를 쌓기도 한 문제이다.
다음에도 좋은 문제로 찾아올 수 있기를..
'취업준비 > 알고리즘 문제 반추' 카테고리의 다른 글
| SWEA : 수영장 문제 [자바][2021.10 기록] (0) | 2021.10.14 |
|---|---|
| 프로그래머스 사이트 문제 정리하기. [20210928시작][최신 갱신: 20210930] (0) | 2021.09.28 |
| 프로그래머스 - 단체사진 찍기 [Level2] [ 카카오 2017 본선] [자바] (0) | 2021.09.15 |
| 2019 카카오 개발자 겨울 인턴십 - 튜플- [프로그래머스][Level2] (0) | 2021.09.10 |
| 프로그래머스 Level2 프린터. [상당히 애먹은 문제..] [ 나만의 풀이 ] (0) | 2021.09.09 |
