[알고리즘] Hash - 위장

JavaScript 스터디에서 알고리즘 문제를 풀고 풀이법을 공유하고 있습니다.

이번 문제는 프로그래머스의 Hash - 위장 문제입니다. 설명과 제한사항을 먼저 보겠습니다. 풀이코드를 바로 보고 싶으시면 여기를 클릭해주세요

• 문제설명

  • 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
  • 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
  • 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

• 제한사항

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

• 입출력 예시

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]; // 5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]; // 3

처음 이 문제를 접했을 때 의상종류를 key로 하고 의상이름들의 배열을 value로 하는 object(Hash 형태 자료형)을 만들고 이걸로 모든 가능한 경우를 다 만들고 그 수를 세면 되겠다고 생각했습니다.

{
  headgear:["yellow_hat", "green_turban"],
  eyewear:["blue_sunglasses"]
}
// 이걸로 1개만 선택하는 경우, 2개 선택하는 경우, 3개 모두 선택하는 경우 다 만들고 그걸 세주면 되지 않을까?

하지만 이 방법은 의상의 종류가 2개 정도일 때는 간단해 보였지만, 3개 이상이 되자 그렇지 못했습니다. 파악해야 할 경우의 수가 너무 많고 또 그걸 동적으로 어떻게 계산해줘야 할지도 난감했거든요. 생각보다 순열/조합의 모든 경우를 찾는 것은 쉽지 않았습니다.

 

결국 스터디원들과 만나 이런 이야기를 하게 되었고 중요한 사실 3가지를 알게 되었습니다.

 

1. 문제의 요지는 모든 "경우의 수"이지 모든 "경우"가 아니다.

즉, 그냥 모든 경우의 수만 산출해서 내놓으면 되는 것이지 굳이 모든 경우를 다 만들 필요는 없다는 것입니다. 만약 headgear의 가짓수가 2개고 eyewear의 가짓수가 1개라면 2*1 => 2로 두 가지 경우의 수를 산출할 수 있습니다.

 

그렇다면 이제 필요한 데이터와 형태는 다음과 같습니다.

{
  headgear: 2,
  eyewear: 1
  // 전체 경우를 다 쓰는게 아니라 경우의 수만 표시해 줍니다.
}

 

하지만 문제가 하나 더 있습니다. 2를 산출한 좀전의 계산은 headgear와 eyewear를 모두 포함하는 경우의 가짓수입니다. 그러나 문제는 headgear와 eyewear 중 하나만 착용하는 경우를 포함합니다. 이렇다면 어떻게 해야 할까요?

 

2. 각 의상 종류의 가짓수에 '입지 않는 경우'를 포함하기 위해 1을 더해주자

이젠 쓰지 않을테지만 이해를 돕기 위해 처음 생각했던 데이터를 갖고 조금 수정해보겠습니다.

{
  headgear:["yellow_hat", "green_turban", "입지 않는 경우"],
  eyewear:["blue_sunglasses", "입지 않는 경우"]
}

만약 이렇게 한다면 각 의상의 가짓수에는 입지 않는 경우가 포함되었고 이걸 선택한 경우의 수는 해당 의상 종류를 입지 않은 것으로 간주하면 됩니다. 그렇다면 위에서 했던 2*1 => 2가 아니라 3*2 => 6이 됩니다. 그럼 답은 6가지로 생각하면 될까요?

 

3. 모든 의상의 종류에서 '입지 않는 경우'를 선택한 경우를 제외하기 위해 전체 결과에서 1을 빼주자

3*2 => 6이라면 6가지의 경우의 수 중에는 headgear도 "입지 않는 경우", eyewear도 "입지 않는 경우"로 선택된 경우가 존재합니다. 이것은 아무 것도 입지 않은 상태인 것으로 '스파이는 하루에 최소 한 개의 의상은 입습니다'라는 제한사항에 어긋나는 경우이므로 이 경우 1가지를 결과값에서 뺍니다. 그럼 최종 결과값은 3*2-1 => 5가 됩니다.

 

이것을 코드로 보면 아래와 같습니다.

 

 

const solution = clothes => {
  let answer = 1;
  let clothesHash = clothes.reduce((a,x) => {
    if(!a[x[1]]) a[x[1]]=1; // '입지 않는 경우'를 포함하기 위해 a의 기본값을 1로 지정합니다.
    a[x[1]]++;
    return a;
  },{})
  for (let props in clothesHash) {
    answer *= clothesHash[props];
  }
  answer = answer - 1; // 모든 의상의 종류를 '입지 않는 경우'로 선택한 경우 한가지를 뺍니다.
  return answer;
}

모든 테스트 케이스를 무사히 통과하였습니다.

 

모든 경우가 아니라 경우의 수만 생각하면 된다는 점, 각 의상 종류에 '입지 않는 경우'를 고려하고, 모든 의상을 '입지 않는 경우'를 전체 경우의 수에서 빼준다는 점, 이 세 가지가 이 문제의 핵심이었던 것 같습니다.

 

모든 경우를 다 구하는건 정말 어렵지만 모든 경우의 수를 구하는건 그렇게 어렵지 않았습니다. 알고리즘 문제는 결국 문제해결력이라는 것을 알게 된 문제였습니다.

 

본문에서 사용된 reduce 메소드 등에 대해서 글을 쓸 기회가 있을 것 같습니다. 당장 사용법이 궁금하시다면 MDN Array.prototype.reduce() 공식문서를 참고해주세요

 

---

더 좋은 코드나 효율적인 코드를 아신다면 댓글로 알려주세요. 많은 분들에게 큰 도움이 될 거에요.

도움이 되셨다면 좋아요와 댓글 부탁드립니다. 감사합니다😁