프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
1. 조합을 이용. ( ABC에서 두 글자 조합으로 만들때 AB , BA는 같은걸로 취급 )
2. hashmap 을 사용하여 orders의 문자열로 만들수 있는 문자열 조합중 course[ ] 에 있는 숫자만큼의 문자열 길이만 조합을 만들어 넣음. 조합을 하기전 orders의 문자열을 알파벳 순으로 정렬을 먼저 진행
ex1 ) course[ ] 가 { 2 , 3 , 4 } 면 2글자 , 3글자 , 4글자 조합만 만들음
ex2 ) orders[ 0 ] 이 "zyx" 이면 알파벳순인 "xyz" 로 정렬 후 진행

3. hashmap의 getOrDefalut를 사용하여 손님들이 주문한 요리조합에서 2번 과정을 거친 문자조합을 카운팅
4. 카운팅해서 만들어진 hashmap 에서 max 카운팅값의 문자열들만 가져와서 정렬. course 에 2가 있어 요리 2개 코스를 추출하는데 max값이 동일한 코스가 여러개인 경우 모두 추출

나의풀이 ( 코드 )
import java.util.*;
class Solution {
public String[] solution(String[] orders, int[] course) {
HashMap<String, Integer> hm = new HashMap<>();
ArrayList<String> arList = new ArrayList<>();
for (int i = 0; i < orders.length; i++) {
char[] charr = orders[i].toCharArray();
Arrays.sort(charr); // 문자열 정렬
for (int j = 0; j < course.length; j++) {
if (charr.length >= course[j]) {
List<String> combinations = generateCombinations(String.valueOf(charr), course[j]);
// 생성된 조합 카운팅
for (String combination : combinations) {
hm.put(combination, hm.getOrDefault(combination, 0) + 1);
}
}
}
}
ArrayList<String> maxString = new ArrayList<>();
// max값들 추출
for (int i = 0; i < course.length; i++) {
int max = 2;
for (String z : hm.keySet()) {
if (hm.get(z) > 1 && z.length() == course[i]) {
if (hm.get(z) == max) {
maxString.add(z);
} else if (hm.get(z) > max) {
maxString.clear();
maxString.add(z);
max = hm.get(z);
}
}
}
for (String maxStr : maxString) {
arList.add(maxStr);
}
maxString.clear();
}
Collections.sort(arList);
String[] answer = arList.toArray(new String[0]);
return answer;
}
// 문자열에서 길이가 length인 중복되지 않는 모든 가능한 조합을 생성하는 함수
public static List<String> generateCombinations(String input, int length) {
List<String> combinations = new ArrayList<>();
generateCombinationsRecursive(combinations, input, length, "", 0);
return combinations;
}
// 재귀적으로 중복되지 않는 조합을 생성하는 함수
public static void generateCombinationsRecursive(List<String> combinations, String input, int length, String current, int index) {
if (current.length() == length) {
combinations.add(current);
return;
}
for (int i = index; i < input.length(); i++) {
generateCombinationsRecursive(combinations, input, length, current + input.charAt(i), i + 1);
}
}
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스/JAVA 자바] 문자열 내 p와 y의 개수 (0) | 2024.04.12 |
|---|---|
| [프로그래머스/JAVA 자바] 마법의 엘리베이터 (0) | 2024.03.04 |
| [프로그래머스/JAVA 자바] 가장 많이 받은 선물 (4) | 2024.01.09 |
| [프로그래머스/JAVA 자바] 소수 찾기 (0) | 2023.12.12 |
| [프로그래머스/JAVA 자바] 다리를 지나는 트럭 (1) | 2023.12.06 |