반응형
https://programmers.co.kr/learn/courses/30/lessons/72411
[ 문제풀이 ]
주어진 orders들로 만들 수 있는 길이가 2 이상인 코스들을 조합한 후 course의 길이마다 최대 주문 횟수를 가지는 코스들을 추출하면 되는 문제이다.
"AC" 코스나 "CA" 코스는 똑같은 코스이기 때문에 조합을 통해 가능한 모든 코스를 추출해주면 된다.
import java.util.*;
class Solution {
Map<String, Integer> hm;
List<Character> list;
class Node {
String str;
int count;
public Node (String str, int idx) {
this.str = str;
this.count = idx;
}
}
public String[] solution(String[] orders, int[] course) {
hm = new HashMap<>();
list = new ArrayList<>();
boolean[] Course = new boolean[11]; //길이가 i인 코스가 존재하는지
int[] maxOrder = new int[11]; //길이가 i인 코스의 최대 주문 횟수
for (int c : course) {
Course[c] = true;
}
for (String order : orders) {
for (int i = 0; i < order.length(); ++i) {
list.add(order.charAt(i));
}
//코스의 조합을 오름차순으로 생성하기 위해
Collections.sort(list);
//길이가 2이상인 코스만 생성
for (int i = 0; i < order.length() - 1; ++i) {
dfs(i + 1, Character.toString(list.get(i)));
}
list.clear();
}
Iterator<String> it = hm.keySet().iterator();
List<Node> nodeList = new ArrayList<>();
//생성한 모든 코스의 조합을 돌면서
while (it.hasNext()) {
String str = it.next();
//주문 횟수가 2이상인 코스만 추출
if (hm.get(str) >= 2) {
nodeList.add(new Node(str, hm.get(str)));
//현재 코스의 길이가 존재하면 최대 주문 횟수 갱신
if (Course[str.length()]) {
maxOrder[str.length()] = Math.max(maxOrder[str.length()], hm.get(str));
}
}
}
List<String> answerList = new ArrayList<>();
//주문 횟수가 최대 주문 횟수인 코스 추출
for (Node node : nodeList) {
if (maxOrder[node.str.length()] == node.count) {
answerList.add(node.str);
}
}
//오름차순으로 정렬
Collections.sort(answerList);
return answerList.toArray(new String[answerList.size()]);
}
public void dfs(int idx, String str) {
//코스의 길이가 2이상일때 주문 횟수 갱신
if (str.length() >= 2) {
if (hm.containsKey(str)) {
hm.replace(str, hm.get(str) + 1);
} else {
hm.put(str, 1);
}
}
if (idx == list.size()) return;
for (int i = idx; i < list.size(); ++i) {
dfs(i + 1, str + Character.toString(list.get(i)));
}
}
}
반응형
'Problem Solving > 카카오 블라인드 기출' 카테고리의 다른 글
2021 - 합승 택시 요금 (0) | 2021.08.09 |
---|---|
2021 - 순위 검색 (0) | 2021.08.09 |
2021 - 신규 아이디 추천 (0) | 2021.08.09 |
2020 - 블록 이동하기 (0) | 2021.08.08 |
2020 - 외벽 점검 (0) | 2021.08.08 |
댓글