[프로그래머스 level2] 위장(해시/java)

오늘도 어김없이 해시와 친해지기 위해 해시문제를 도전!!

 

저번에 올렸던 해시 레벨1 문제를 기억하면서 풀어보기 도즈언!!

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은

청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return하도록 solution함수를 작성해주세요.

 

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_'로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

 

입출력 예 설명

예제 #1

headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로

아래와 같이 5개 조합이 가능합니다.

예제 #2

face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

 

---

나의 문제 풀이

 

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
    	int answer = 1;
		int cnt = 1;
		HashMap<String, Integer> hm = new HashMap<String, Integer>(); 
		for (String[] i : clothes) {
			if (hm.containsKey(i[1])) {   //key중복되면 cnt++
				cnt++;
			}
			hm.put(i[1], cnt);      // {key,개수}
		}

		Iterator<String> keys = hm.keySet().iterator();
		ArrayList<Integer> arr = new ArrayList<Integer>();
		for (int i = 0; i < hm.size(); i++) {
			arr.add(hm.get(keys.next()));        //arraylist에 담아서 뽑기쉽게..?
		}
		for (int i = 0; i < arr.size(); i++) {
			answer *= (arr.get(i) + 1);     //arraylist에서 뽑아서 비교  
		}                                   //이쪽 부분은 생각을 잘 못해내서 다른 블로그 참고함..
		return answer-1;
    }
}

나는 위처럼 조금 참고를 하고 테스트가 둘다 통과되길래 혹시나 체점해보았지만

역시나,,, 정확성21.4..ㅋㅋㅋ

후.. 멀었다..

 

해시 level1문제에서 처럼 getOrDefault메소드를 사용하려다 containsKey메소드를 사용했다.

이부분이 에러였다. 다시 생각해보니 cnt를 왜 저렇게 했지.. 중복되는 아이템이 한개면 상관없는데 

중복되는게 여러개면 cnt는 계속 오르니까 문제가 되는거였다..

 

그리고 나는 answer *= ( 벨류+1);     -> return answer-1;   여기를 생각해내지 못했다..

answer *= ( 옷의 가지수 + 안 입을 경우(1) )   << 모든 경우의 수를 구해서 모두 안입는 경우를 빼는 방법이다..

 

아무튼 제가 참고한 더 깔끔한 코드를 한번 봅시다!

---

 참고한 코드

    public int solution(String[][] clothes) {
       int answer = 1;

        Map<String, Integer> clothesMap = new HashMap<>(); // 종류 : 갯수

        for (int i = 0; i < clothes.length; i++) {
            // 종류 여부 판단. 같은 종류 일 경우 Value + 1
            clothesMap.put(clothes[i][1], clothesMap.getOrDefault(clothes[i][1], 0)+1);
        }

        // 경우의 수 체크 answer *= (옷 가지수 + 안 입을 경우)
        for (int val : clothesMap.values()){
            answer *= (val+1);
        }

        // 모두 다 안입는 경우는 존재하지 않으므로 -1
        return answer-1;
    }

제가 참고한 블로그의 내용의 해설에 따르면

 

1. (headgear의 수 + 1) 1을 더 해주는 이유는 headgear를 착용하지 않을 수도 있기 때문입니다.
2. (eyewear의 수 + 1 ) 1을 더 해주는 이유는 eyewear를 착용하지 않을 수도 있기 때문입니다.
3. 두 수는 각각 독립적이기 때문에 1번 2번의 수를 곱하고 - 1 (모두 안입는 경우는 존재하지 않으므로)

getOrDefault 메소드는 첫번째 인자의 값이 Map에 존재하지 않는다면 Default로 설정한 값으로 가져오게 됩니다. NULL을 방지하기 위해 사용하였습니다.

 

이렇게 설명해주셨다..

 

코드도 훨씬 간결하고 테스트케이스도 모두 통과하는 좋은 해답이였다!!

 

위처럼 경우의수를 뽑아 낼 수 있는 알고리즘을 잘 짤수 있도록 수학적인 사고를 더 높이도록 노력하자..!!

 

 

추가 다른사람 풀이에서

좋아요 가장 높은 풀이

import java.util.*;
import static java.util.stream.Collectors.*;

class Solution {
    public int solution(String[][] clothes) {
        return Arrays.stream(clothes)
                .collect(groupingBy(p -> p[1], mapping(p -> p[0], counting())))
                .values()
                .stream()
                .collect(reducing(1L, (x, y) -> x * (y + 1))).intValue() - 1;
    }
}

프로그래머스 내에서 가장 좋아요를 많은 풀이이다.

우선 이 해설은 풀이보단 참고하도록 하자..

 

 

나는 stream과 collection에 대해 잘 알지 못한다.. 

hash에 대해 익숙해 지면 collection과 stream에 대해 알아보고 공부해야겠다!

 

 

 

 

 

 

 

 

참고😁

https://velog.io/@giraffelim/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9C%84%EC%9E%A5

프로그래머스 - 위장