· 문제 설명
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
| 종류 | 이름 |
| 얼굴 | 동그란 안경, 검정 선글라스 |
| 상의 | 파란색 티셔츠 |
| 하의 | 청바지 |
| 겉옷 | 긴 코드 |
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
· 제한 사항
clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
스파이는 하루에 최소 한 개의 의상은 입습니다.
· 입출력 예
| clothes | return |
| [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]] | 5 |
| [[crow_mask, face], [blue_sunglasses, face], [smoky_makeup, face]] | 3 |
· 입출력 예 설명
예제 #1
headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.
1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses
예제 #2
face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.
1. crow_mask
2. blue_sunglasses
3. smoky_makeup
· Thinking 1
a b c : 3 + 3 + 1 = 7
1개 a, b, c -> 3
2개 ab, ac, bc -> 3
3개 abc -> 1
a1 a2 b : 3 + 2 = 5
1개 a1, a2, b -> 3
2개 a1b, a2b -> 2
a b c d : 4 + 6 + 4 + 1 = 15
1개 a b c d -> 4
2개 ab ac ad bc bc cd -> 7
3개 abc abd acd bcd -> 4
4개 abcd -> 1
a1 a2 b c : 4 + 5 + 2 = 11
1개 a1, a2, b, c -> 4
2개 a1b, a1c, a2b, a2c, bc -> 5
3개 a1bc, a2bc -> 2
a1 a2 b1 b2 : 4 + 4 = 8
1개 a1, a2, b1, b2 -> 4
2개 a1b1, a1b2, a2b1, a2b2 -> 4
갯수가 3개 / 종류가 3개 -> 3 + 3 + 1 = 7 -> 3C1 + 3C2 + 3C3
갯수가 3개 / 종류가 2개 -> 3 + 2 = 5 -> 3C1 + ??? // 종류의 갯수만큼만 포문을 돌리면 됨
갯수가 3개 / 종류가 1개 -> 3 -> 3C1
갯수가 4개 / 종류가 4개 -> 4 + 6 + 4 + 1 = 15 -> 4C1 + 4C2 + 4C3+ 4C4
갯수가 4개 / 종류가 3개 -> 4 + 5 + 2 = 11 -> 4C1 + ??? + ???
갯수가 4개 / 종류가 2개 -> 4 + 4 = 8 -> 4C1 + ???
갯수가 4개 / 종류가 1개 -> 4 -> 4C1
3C1 = 3! / 1! * (3-1)! -> 3
3C2 = 3! / 2! * (3-2)! -> 3
3C3 = 3! / 3! -> 1
4C1 = 4! / 1! * (4-1)! -> 4
4C2 = 4! / 2! * (4-2)! -> 6
4C3 = 4! / 3! * (4-3)! -> 4
4C4 = 4! / 4! -> 1
· Thinking 2
일단 종류를 구하고 / 갯수를 구함 !!
갯수 4 종류 3 :
2개를 뽑는 경우에는 서로를 포함해서 뽑는 경우 (1)이 빠지고
3개를 뽑는 경우에는 서로를 포함해서 뽑는 경우(2)이 빠지고
같은 종류를 제외한 나머지 종류의 수만큼이 빠지네
· Thinking 3
종류별로 정렬하고 종류 갯수 알아내기 (String 2차원 배열 정렬)
Arrays.sort(clothes, new Comparator<String[]>() {
@Override
public int compare(final String[] entry1, String[] entry2) {
final String time1 = entry1[1];
final String time2 = entry2[1];
return time1.compareTo(time2);
}
});
· 완성 코드
import java.util.HashMap;
class Solution {
public int solution(String[][] clothes) {
int answer = 1;
HashMap<String, Integer> kind = new HashMap<>();
for (int i = 0; i < clothes.length; i++) {
String type = clothes[i][1];
if (!kind.containsKey(type)) {
kind.put(type, 0);
}
kind.put(type, kind.get(type)+1);
}
String[] keys = kind.keySet().toArray(new String[0]);
for (int i = 0; i < keys.length; i++) {
answer *= (kind.get(keys[i]) + 1);
}
return answer-1;
}
}다른 사람의 질문에 대한 답 참고..ㅠㅠ
- 참고한 답변 :
가능한 모든 조합을 직접 구해서 계산할 필요가 없습니다.
예를들어 머리:3, 얼굴:2, 옷:1 이라면 총 가능한 개수는
(3+1) * (2+1)*(1+1) -1 = 13
+1씩을 더한 것은 착용하지 않은 경우가 추가 되기 때문이고 마지막으로 -1을 한것은 모든 부위를 입지 않은 경우는 없기 때문입니다.
· 문제 출처
https://programmers.co.kr/learn/courses/30/lessons/42578
알고리즘 연습 - 위장 | 프로그래머스
programmers.co.kr
댓글