코드굽는 타자기
Programmers[42578] - 위장[Level2] 본문
링크
문제설명
- 조합 경우의 수
문제풀이
- 조합 경우의 수 = 종류별 가능한경우 다 곱한 후, 아무것도 안고른 경우 빼기
문제코드
import java.util.HashMap;
public class Solution42578_위장 {
public static int solution(String[][] clothes) {
// {종류 , 종류개수}
HashMap<String, Integer> hm = new HashMap<String, Integer>();
for (String[] cloth : clothes) {
if(hm.containsKey(cloth[1])){
hm.put(cloth[1], hm.get(cloth[1])+1);
}
else {
hm.put(cloth[1],1);
}
}
int answer = 1;
for (int val : hm.values()) {
answer*=(val+1);
}
return answer-1;
}
public static void main(String[] args) {
System.out.println(solution(new String[][] {
{"yellow_hat", "headgear"},
{"blue_sunglasses", "eyewear"},
{"green_turban", "headgear"}
}));
System.out.println(solution(new String[][] {
{"crow_mask", "face"},
{"blue_sunglasses", "face"},
{"smoky_makeup", "face"}
}));
}
}
아쉬운점
-
사실 해쉬문제라 하기에는 종류의 개수가 5개뿐이라.. 굳이 해쉬 써야하나 싶기도 함.
- 해쉬 구현에 의의를 두자.
-
Iterator 쓰는 법을 모름
-
Iterator<Integer> it = map.values().iterator(); while(it.hasNext()) { answer *= it.next().intValue()+1; }
이렇게 사용한다.
다른사람 풀이
- dp로 풀 수 있음
- 종류N선택안했을 경우 = NX, 종류N선택 = NO 로 표시한다
- ~N은 N종류까지 선택했을 경우를 의미
1X | 1O |
~2X = 1X * 2X + 1O * 2X | ~2O = 1X * 2O + 1O * 2O |
~3X = ~2X * 3X + ~2O * 3X | ~3O = ~2X * 3O + ~2O * 3O |
... | ... |
~NX = ~(N-1)X * NX + ~(N-1)O * NX | ~NO = ~(N-1)X * NO + ~(N-1)O * NO |
- ~N = ~NX + ~NO인데 여기서 1X2X...NX인 경우 1 빼주면 된다.
- dp로는 생각도 못했는데 dp적 사고를 개발하기 좋은 접근법인 것 같다.
'알고리즘 > 해시' 카테고리의 다른 글
Programmers[42579] - 베스트앨범[Level2] (0) | 2020.04.30 |
---|---|
Programmers[42577] - 전화번호 목록도움말[Level2] (0) | 2020.04.30 |
Programmers[42576] - 완주하지 못한 선수[Level1] (0) | 2020.04.30 |
Programmers[64063] - 호텔 방 배정[Level4] (0) | 2020.04.05 |
Comments