[프로그래머스] 위장 - Hash
2020. 10. 8. 22:37ㆍAlgorithm
반응형
SWIFT로 Hash 문제에 대해서는 풀어봤었습니다.
하지만 Java로는 Hash 자료구조 문제를 풀어본 적이 없어서 프로그래머스의 문제를 풀어보았습니다.
문제는
스파이가 매일 다른 옷의 조합을 입어야 하는데,
처음 clothes 이차원 배열의 형태로 (옷의 종류, 옷의 이름)이 주어지고 이를 이용해서 만들 수 있는 조합의 수를 찾는 것입니다.
단, 스파이는 꼭 한 종류의 옷을 하나는 입어야합니다.
즉, 하나도 안 입는 경우는 존재하지 않습니다.
Hash문제이기 때문에, 우선 문제를 해결하기 위해 (key, value)의 형태로 HashMap을 만들어야합니다.
HashMap<String, Integer> clothes_set = new HashMap<>();
for (int i = 0; i < clothes.length; i++) {
if (clothes_set.get(clothes[i][1]) == null) {
clothes_set.put(clothes[i][1], 1);
} else {
clothes_set.put(clothes[i][1], clothes_set.get(clothes[i][1]) + 1);
}
}
다음과 같이 초기화하였습니다.
그런데 여기서 왜 Integer을 활용하여 초기화하였을까요...?
저도 처음에는 조합을 만들려고 하였으나 생각해보니 조합의 수만 구하기 때문에, 확률과 통계 때 배웠던 조합의 수를 구하는 식을 적용하기 위해서 였습니다.
만약 3가지의 종류의 옷이 있는데 각각 (1, 5, 4)개의 옷을 가지고 있으면,
조합의 수는 (1 * 5 * 4)가 됩니다.
그렇다면 이번 문제에서는 어떻게 적용할까요?
안 입는 경우도 존재하기 때문에, 각 종류별로 +1을 하였습니다.
그리고 마지막으로 전부 안입는 경우는 안된다고 분명히 조건에 명시되어 있죠⁉️
이를 위해, -1을 해주었습니다.
int answer = 1;
for (String key : clothes_set.keySet()) {
answer *= clothes_set.get(key) + 1;
}
answer -= 1;
각 종류의 key에 해당하는 옷의 수를 가져오고,
+1을 해서 답에 곱해주었습니다. 그리고 마지막으로 -1을 해주면 답을 알 수 있습니다.
전체 소스코드는
import java.util.HashMap;
class Solution {
public int solution(String[][] clothes) {
int answer = 1;
HashMap<String, Integer> clothes_set = new HashMap<>();
for (int i = 0; i < clothes.length; i++) {
if (clothes_set.get(clothes[i][1]) == null) {
clothes_set.put(clothes[i][1], 1);
} else {
clothes_set.put(clothes[i][1], clothes_set.get(clothes[i][1]) + 1);
}
}
for (String key : clothes_set.keySet()) {
answer *= clothes_set.get(key) + 1;
}
return answer - 1;
}
}
반응형
'Algorithm' 카테고리의 다른 글
[프로그래머스] 단어 변환 - BFS (0) | 2020.10.18 |
---|---|
[백준 11053번] 가장 긴 증가하는 수열 - DP (0) | 2020.10.15 |
[백준 2217번] 로프 - Greedy Algorithm (0) | 2020.10.04 |
[백준 2156번] 포도주 시식 - DP (0) | 2020.10.02 |
[백준 1912번] 연속합 - DP (0) | 2020.09.30 |