정말 한 달도 넘게 알고리즘 문제풀이를 쉬었다..! 프로젝트 개발하느라 바빴다는 건 핑계고 너무 게으른 2월을 보낸 게 아닌가 싶다 ! 정말 코테 떨어지면 스스로한테 실망할 거 같은데 ㅠㅠ 다시 열쉬미 해봐야겠다 !
이번에 푼 문제는 프로그래머스 고득점 키트의 해시 분류에 있는 level2 문제다 !
https://programmers.co.kr/learn/courses/30/lessons/42578
문제 설명
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
| 종류 | 이름 |
|---|---|
| 얼굴 | 동그란 안경, 검정 선글라스 |
| 상의 | 파란색 티셔츠 |
| 하의 | 청바지 |
| 겉옷 | 긴 코트 |
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
- 스파이는 하루에 최소 한 개의 의상은 입습니다.
입출력 예
| clothes | return |
|---|---|
| [["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]] | 5 |
| [["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]] | 3 |
풀이 방법
풀이 방법은 간단하다 ! 주어진 옷들로 몇 가지 조합을 만들 수 있는지 경우의 수를 생각해보면 된다. 같은 종류의 옷은 하나만 고를 수 있다는 것과 모든 옷의 종류를 입지 않아도 된다는 것을 고려하여, 종류에 포함된 옷의 개수에 1을 더한 값들을 ( 입지 않는 경우를 더해준다 ) 모두 곱해주면 된다. 이 때, 최소 한 개의 의상은 입어야 하므로 1을 빼준 값이 최종 결과 값이 된다.
이 문제는 경우의 수를 생각해서 간단하게 해결할 수 있다. 이 때, 옷의 종류를 key값, 옷의 이름을 value로 하여 각 종류에 해당하는 옷이 몇 개인지 파악하는 부분에서 해시의 아이디어가 들어가고, 다양한 구현 방법이 생각났지만 본인은 hashmap을 사용하였다.
hashmap, hashtable, hashset 중 어떤 것을 쓸까 고민했지만, 같은 이름을 가진 의상은 존재하지 않기에 set류나 map류나 동일하게 동작하며, 동기화 역시 의미없기에 가장 익숙한 hashmap을 사용하기로 선택하였다. 결과적으로 동일하지만 구현된 코드에 따라서 약간의 효율성의 차이가 있으려나라는 생각이 들어 이번 기회에 세 개의 collection 내부 코드를 읽어봐야겠다고 생각했다.
코드
import java.util.HashMap;
public class Solution {
public static int solution(String[][] clothes) {
int answer = 1;
HashMap<String, Integer> items = new HashMap();
for (String[] clothe : clothes) {
if(items.get(clothe[1]) == null) items.put(clothe[1], 1);
else items.put(clothe[1], items.get(clothe[1])+1);
}
for(String key : items.keySet()) answer = answer * (items.get(key) + 1);
return answer-1;
}
public static void main(String[] args) {
}
}