[코딩테스트-JAVA]위장 풀이 - 초보도 이해하는 풀이(프로그래머스)

안녕하세요

인포돈 입니다.

프로그래머스 위장 풀이입니다. 

* 참고사항
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

프로그래머스 (위장)

문제 설명

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

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

 

스파이가 가진 의상들이 담긴 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
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

---

성공코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<>();
        
        for(int i = 0 ; i < clothes.length ; i ++){
            map.put(clothes[i][1],map.getOrDefault(clothes[i][1],0)+1);
        }
        
            Set<String> set = map.keySet();
            for(String str : set){
                answer*=map.get(str)+1;
            }
        
        
        
        return answer-1;
    }
}

위장 알고리즘에서 hashmap을 활용하여 문제를 해결하였습니다. 우선적으로 해당 문제의 카테고리가 해쉬로 구분되어 있기에 해쉬를 사용하였고, 그 외의 풀이도 있음을 알려드립니다.

---

알고리즘 흐름도

해시 맵 선언

-> 반복문을 이용하여 맵에 가짓수를 다 더해줍니다. (getOrDefault 메서드 사용)

-> 해쉬 맵 키값 반복을 위하여 set에 키값을 저장한다.

-> 저장한 set을 통하여 반복문을 돌려 정답에 가짓수를 더해준다.

-> 마지막에 -1을 해주어 반환해 준다.

 

---

알고리즘 흐름도를 쉽게 이해하기 위해서 STEP을 따라가면서, 하나하나 알려드리겠습니다.

 

간단히 hashmap에 대해서 설명해 드리면 <key, value> 이렇게 한쌍의 값을 하나의 배열에 저장한다고 보시면 됩니다. 기존에 저희는 인덱스로 배열을 관리하는데 그 인덱스가 바로 key로 바뀌었고, 그 key값을 숫자가 아닌 문자로도 가능하게 해 줍니다.

 

STEP1 반복문을 이용하여 맵 가짓수 더해주기

        for(int i = 0 ; i < clothes.length ; i ++){
            map.put(clothes[i][1],map.getOrDefault(clothes[i][1],0)+1);
        }

해당 코드에서 알아야 할 점은 put 메서드와 getOrDefault 메서드입니다.

 - put메서드

map.put(key값, value값)을 넣어주어 해쉬 맵에 값을 추가해주는 메서드입니다.

 

key값으로 clothes [i][1]이 들어가게 되면 바로 카테고리가 key값이 되게 되죠. 즉, headgear, eyewear, face와 같이 카테고리가 key값이 되는 거죠.

 

 - getOrDefault 메서드

map.getOrDefault(key값, value초기값) 이런 식으로 사용을 하고 의미는 바로 해당 map에 해당 key값이 존재하면 해당 key에 맞는 value값을 반환해 주고, 아니면 value초기값으로 넣어준 값이 반환되게 됩니다.

즉, 해당 key가 있으면 해당 값에 +1을 해주고

 없으면 기본값인 0에 +1을 해주는 메서드이죠.

 

이렇게 되면, 이제 해당 카테고리에 몇 개의 옷들이 들어가 있는지 알 수 있게 되죠.

 

---

STEP2 해쉬 맵 반복하기(KEY값 이용)

우선적으로 해쉬 맵은 배열처럼 인덱스가 아니기 때문에 일반적인 반복문을 통해서는 해쉬 맵을 순회 하여 출력할 수 없습니다. 그렇기 위해서는 순서를 지정할 수 있는 SET타입의 배열로 바꾸어 주어야 합니다.

 

여기서 set이 무엇인지 정확히 모르셔도 됩니다. int, short, float, string과 같이 데이터 타입으로 이해하시면 되고, map에 있는 key값을 해당 set타입으로 바꿔줘야 합니다.

Set<String> set = map.keySet();

이런 식으로 말이죠. 해쉬 맵이나 모든 맵에서는 keySet() 메서드를 통해서 간편히 key값만 가져와 set타입의 변수에 넣어줄 수 있습니다.

 

그러면 저희는 이제 해쉬 맵을 반복문을 통해 순회를 할 수 있게 되죠.

---

STEP 3 반복문을 활용하여 정답 값 넣기

 

정답 값을 넣기 전에 저희는 가짓수를 개산 하는 방법을 알아야 합니다. 뭐 이거는 코딩의 실력보다는 수학적 사고력이 필요한 부분이니, 한 번쯤 생각해보셔야 합니다... ㅎㅎ

 

예를 들어 A, B, C라는 3개의 카테고리가 있다고 생각해 봅시다. 각 카테고리에는 카테고리에 맞는 옷들이 있겠죠.

 

각 카테고리별로 1개씩 입을 수 있다고 한다면, 경우의 수는 (A 카테고리의 수 + 1)*(B 카테고리의 수 +1)*(C 카테고리의 수 +1)의 값을 갖게 됩니다.

 

그러나 마지막에 -1을 해주어야 하는데 그 이유는 어떠한 카테고리도 입지 않는 경우의 수도 포함하기 때문입니다~

           for(String str : set){
                answer*=map.get(str)+1;
            }
        

결론적으로 앞서 STEP2에서 변환했던 KEY값들을 저장한 set변수를 이용하여 반복을 통해 해당 값들을 답에 넣어주고 마지막 반환을 할 때 -1만 해주면 해당 알고리즘은 끝!!