https://school.programmers.co.kr/learn/courses/30/lessons/72411
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
LEVEL 2, 풀이법 : 순/조/부 + HashMap , 풀이 시간 1h
<step 1> 메뉴를 모두 오름차순으로 될 수 있도록 정렬한다.
//1. orders 메뉴 정렬
for(int i = 0; i < orders.length; i++){
char[] arr = orders[i].toCharArray();
Arrays.sort(arr);
orders[i] = String.valueOf(arr);
}
<step 2> Combination으로 길이 별 모든 경우의 수를 확인한다.
public void Combi(String order, String others, int depth){
if(order.length() == depth){
hashMap.put(order, hashMap.getOrDefault(order, 0) + 1);
return;
}
for(int i = 0; i < others.length(); i++){
Combi(order + others.charAt(i), others.substring(i+1), depth);
}
}
<step 3> course 에 맞는 길이와 모든 경우의 수를 확인한다
// 2. course에 맞게 조합 뽑기.
for(int c : course){
for(String o : orders){
Combi("", o, c);
}
// 3. 길이 별로 max값 뽑기
if(!hashMap.isEmpty()){
List<Integer> countList = new ArrayList<>(hashMap.values());
int m_value = Collections.max(countList);
if(m_value > 1){
for(String k : hashMap.keySet()){
if(hashMap.get(k) == m_value){
answerList.add(k);
}
}
}
hashMap.clear();
}
}
<전체 코드>
import java.util.*;
class Solution {
static ArrayList<String> answerList = new ArrayList<>();
static Map<String, Integer> hashMap = new HashMap<>();
public String[] solution(String[] orders, int[] course) {
//1. orders 메뉴 정렬
for(int i = 0; i < orders.length; i++){
char[] arr = orders[i].toCharArray();
Arrays.sort(arr);
orders[i] = String.valueOf(arr);
}
// 2. course에 맞게 조합 뽑기.
for(int c : course){
for(String o : orders){
Combi("", o, c);
}
// 3. 길이 별로 max값 뽑기
if(!hashMap.isEmpty()){
List<Integer> countList = new ArrayList<>(hashMap.values());
int m_value = Collections.max(countList);
if(m_value > 1){
for(String k : hashMap.keySet()){
if(hashMap.get(k) == m_value){
answerList.add(k);
}
}
}
hashMap.clear();
}
}
Collections.sort(answerList);
String[] answer = new String[answerList.size()];
for(int i = 0; i < answerList.size(); i++){
answer[i] = answerList.get(i);
}
return answer;
}
public void Combi(String order, String others, int depth){
if(order.length() == depth){
hashMap.put(order, hashMap.getOrDefault(order, 0) + 1);
return;
}
for(int i = 0; i < others.length(); i++){
Combi(order + others.charAt(i), others.substring(i+1), depth);
}
}
}'Algorithm Study > java' 카테고리의 다른 글
| 프로그래머스 - [3차] 압축 (0) | 2024.04.02 |
|---|---|
| [프로그래머스] 전략망을 둘로 나누기 (풀이 : union-find & dfs) (0) | 2024.03.20 |
| Union-Find 알고리즘(서로소 집합, Disjoint-Set) (0) | 2024.03.20 |
| [백준 - Java] 2565 - 전깃줄 (0) | 2024.02.20 |