[프로그래머스] 해시 - 위장 문제 풀이

이번에는 프로그래머스에서 해시 문제 중 "위장" 문제 풀이를 해보겠습니다.

해시는 지난 완주하지 못한 선수 문제 풀이에서 다뤄봤던 알고리즘으로 해시 맵 자료구조를 활용하여 문제를 풀이하는 것이 중요한 점이라고 말할 수 있습니다.

혹시 해시 - 완주하지 못한 선수 문제 풀이를 보지 않으셨다면 보고 아래 문제 풀이에도 참고하시기 바랍니다.

 

 

 

2022.06.15 - [분류 전체보기] - [프로그래머스] 해시 - "완주하지 못한 선수" 문제 풀이(Hash 활용)

[프로그래머스] 해시 - "완주하지 못한 선수" 문제 풀이(Hash 활용)

 

 

 

 

위 완주하지 못한 선수 문제 풀이(Hash 활용) 버전 포스팅을 보고 오셨다면 이제 해시 - 위장 문제 풀이를 해보겠습니다.

 

 

프로그래머스 > 해시 > 위장 문제 풀이

 

 

 

 

》 문제 정보

• 문제명: 위장
• 문제 난이도: Level 2
• 문제 푼 사람수: 35225명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

 

》 문제 설명

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

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

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

 

 

이 문제는 가지고 있는 옷의 종류를 알고 있을 때, 옷을 다르게 입을 수 있는 조합의 수를 반환하는 문제입니다.

그럼 이 문제를 간단히 정리해보겠습니다.

 

• 가진 옷에 대하여 다르게 입을 수 있는 옷의 조합 수 구하기
• Inputs
  • clothes: 가지고 있는 옷에 대한 정보를 담은 2차원 배열
• Output: 서로 다른 옷 입는 조합 갯수

 

 

 

 

》 제한사항

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

 

 

위 제한사항에서 정말 중요한 사항들이 많이 있습니다. 제한사항 내용을 풀어서 해석보겠습니다.

• 입력 값인 clothes의 각 행 = [옷 이름, 옷 종류]
• 1 ≤ 의상 수 ≤ 30
• 이름이 같은 옷은 없으며, 옷 이름, 옷 종류는 모두 문자열(string)
• 1 ≤ 문자열의 길이(a-z, _) ≤ 20
• 최소 1개의 옷은 입는다.
  (즉, 모든 종류에 따라 1개씩 입는 것이 아니라 최소로 1종류만 입을 수 있다.)

마지막 제한사항의 내용이 정말 키 포인트입니다.

 

 

 

 

》 입출력 예

clothes	return
[["yellow_hat", "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

 

 

 

 

》 알고리즘 만들기

위 문제는 하나의 알고리즘만 알면 쉽게 풀 수 있는 문제로 보입니다. 여기서 필요한 알고리즘은 각 종류별 선택지가 여러개 있는 상황에서 각 종류별 하나를 선택하여 만들 수 있는 조합 개수 구하는 방법입니다. 저는 학생 때 수학문제 풀 때 활용했던 기억이 났습니다.

 

 

문제 풀이에 필요한 알고리즘을 간단한 예로 도식화된 이미지로 알아보겠습니다.

 

 

 

 

즉, 위 문제를 풀기 위한 알고리즘 정의는 아래와 같습니다.

 

 

A 종류: a개, B 종류: b개 ... 의 각 선택하는 조합 수 구하기  ▶▶  a X b X ...

 

 

서로 다른 조합을 만드는 방법은 각 선택할 수 있는 종류를 곱한 값이라는 것 입니다.

그럼 문제 풀이에 필요한 알고리즘을 확인해보았으므로, 위 개념을 활용한 문제 풀이용 알고리즘을 만들어보겠습니다.

 

 

1. clothes를 순회하면서 입력된 모든 종류에 대한 옷의 개수를 구한다.
2. 모든 종류에 대해 순회하면서 옷의 개수에 1을 더한 값을 곱한다.
    ※ 해당 종류의 옷을 입지 않은 케이스를 포함하여 곱한다.
3. 최종 곱한 결과에서 1을 뺀 값을 반환한다.
    ※ 모두 입지 않은 케이스를 제외한다.

 

 

 

 

》 코드 구현

function solution(clothes) {
    let answer = 1;
    const clothesMap = [];
    
    // 1. clothes를 순회하면서 입력된 모든 종류에 대한 옷의 개수를 구한다.
    clothes.map((cloth) => clothesMap[cloth[1]] = (clothesMap[cloth[1]]|0)+1)
    
    // 2. 모든 종류에 대해 순회하면서 옷의 개수에 1을 더한 값을 곱한다.
    for(let clothes in clothesMap) {
       answer *= (clothesMap[clothes] + 1); 
    }
    
    // 3. 최종 곱한 결과에서 1을 뺀 값을 반환한다.
    return answer-1;
}

 

 

위 코드 구현은 정말 짧습니다. 그 이유는 알고리즘에 함축되어있다고 생각하며, 이 문제의 핵심은 해시를 활용해서 문제를 푼다기 보단, 조합 수를 구하기 위한 방법을 떠올려 알고리즘을 만드는 것이 더 중요하다고 생각합니다.

 

 

 

 

》 채점 결과

 

 

이 문제는 정확성 테스트 케이스만 28개입니다. 참고하여 문제 푸시기 바랍니다. 여러분도 이런 문제를 풀면서 머리가 굴러가는 재미를 느끼셨으면 좋겠습니다. 또한 28개의 통과 문구를 확인하여 100점 만점이라는 결과를 손에 넣으며 뿌듯함도 함께 느끼셨으면 좋겠습니다.