[프로그래머스] 의상

Programmers : 의상

 

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

---

💬 문제

 해시(hash) 에 대한 이해가 있다면, 충분히 풀 수 있는 문제였다.

해시에 대해 익숙하지 않다면, 아래 글을 참고해보길 바란다.

 

https://valueengine.tistory.com/55

[자료구조] 해시 (Hash)

 

💬 문제 설명

1. 입어야 할 의상이 [이름, 종류]의 형태로 또다른 배열 내에 들어간 2차원 배열 clothes가 주어진다.
   
   - 각 종류별로 최대 1가지 의상만 착용할 수 있다
   
   - 최소 1개 이상의 의상을 입어야 한다
   
   - 같은 이름의 의상이 존재하지 않는다
   
   
2. 서로 다른 옷의 조합으로 입을 수 있는 경우의 수를 출력해준다.

 

728x90

 

---

💡 입출력 예시

첫 번째 예시를 보면, headgear에 해당하는 의상이 yellow_hat과 green_turban 2개가 있고, eyewear에 해당하는 의상이 1개 주어져있다.

이때 headgear를 쓰거나 쓰지 않을 경우의 수는 총 3가지다 (아무것도 쓰지 않을 경우, yellow_hat, green_turban)

그리고 eyewear를 쓰거나 쓰지 않을 경우의 수는 총 2가지다 (아무것도 쓰지 않을 경우, eyewear)

 

headgear와 eyewear를 쓰는 것은 서로 별개이기(독립적이기) 때문에 각 경우의 수를 곱해주면 서로 다른 의상을 입을 수 있는 총 경우의 수 6이 나온다.

다만, headgear도 eyewear도 쓰지 않는 경우가 총 경우의 수 6에 포함되어 있기에 1을 빼줘야 한다.

 

 

반응형

 

---

💻 풀이

이 문제는 의상 이름과 종류가 짝을 이루고 있기에 해시 테이블로 풀 수 있다.

 해시 테이블(hash table) 은 key와 value로 데이터를 저장하는 자료구조이다.

🔑 풀이 : 해시 (hash)

• reduce 메서드를 통해 clothes를 해시 테이블로 바꿔준다.
  
  - 테이블에 특정 종류의 옷이 있다면 +1로 수를 늘려주고, 없다면 1을 할당해준다
  
  
• for ... in문을 통해 table의 key를 통해 value를 뽑아내준다.
  
  - value는 특정 종류의 의상의 수다
  
  - 특정 종류의 의상을 입지 않을 경우를 고려해줘야 하므로 1을 더해준다
  
  - 각 종류의 의상을 입을 경우의 수는 서로 독립적이므로 곱해 총 경우의 수를 뽑아내준다
  
  
• 그 어떤 종류의 옷도 입지 않을 경우의 수 1을 빼준다.

function solution(clothes) {
    let ans = 1;
    
    // 각 종류의 개수 카운트
    let table = clothes.reduce(
        (table, key) => {
            table[key[1]] = table[key[1]] ? table[key[1]] + 1 : 1;
            return table;
        }, {}
    );
    
    // 착용 가능한 경우의 수 카운트
    for (let key in table) {
        ans *= (table[key] +1);  // 특정 종류를 입지 않을 경우 +1
    }
    // 아무것도 입지 않은 경우 제외
    return ans -1;
}

👣 예제를 참고한 풀이

1번째 예제

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]

 

1번째 예제를 해시 테이블로 바꿔주면 다음과 같다.

{ headgear: 2, eyewear: 1 }

 

for ... in문을 통해 뽑아낸 value 값은 2와 1이고, 각 종류의 옷을 입지 않을 경우를 더해주면 3과 2가 된다.

headgear를 쓰는 것과 eyewear를 쓰는 것은 서로 독립적이므로 3과 2를 곱해 6이 나오지만, 두 종류 모두 쓰지 않을 경우를 빼면 5가 된다.

 

 

실행 결과와 채점 결과는 다음과 같다.

 

 

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️