프로그래머스 코딩테스트 연습 Level 2 - 위장 (JavaScript/Python)

프로그래머스 코딩테스트 연습 Level 2 - 위장 (JavaScript/Python)

 

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중 해시(Hash) 관련 문제인,

[위장] 문제를 JavaScript 와 Python를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

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

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

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

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

제한사항

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

 

입출력 예

clothes	return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow_mask", "face"], ["blue_sunglasses", "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

 

작성한 답

solution.js

function solution(clothes) {
    return Object.values(clothes.reduce((ac, [_, k]) => {
        ac[k] = (ac[k] ?? 0) + 1;
        return ac;
    }, {})).reduce((ac, v) => ac * (v + 1), 1) - 1;
}

solution.py

def solution(clothes):
    answer = 1
    dic = {}
    for v, k in clothes:
        if not k in dic:
            dic[k] = 0
        dic[k] += 1
        
    for v in dic.values():
        answer *= v + 1
        
    return answer - 1

 

설명

해시, 경우의 수, 곱셈 공식을 이해한다면 문제를 해결할 수 있습니다!

 

먼저 옷의 종류별 개수를 구해줍니다. JavaScript에서는 reduce, Python에서는 dict를 사용할건데 여러가지 방식으로 하실 수 있겠지만 저같은 경우 위와 같이 작성해 보았습니다.

JavaScript 와 Python의 코드가 달라보일 수는 있으나 완전히 똑같은 방식입니다. 작성한 방식의 차이일 뿐입니다!

Python의 코드가 어떤 방식으로 돌아가는지 이해하기 훨씬 쉬운 방법으로 작성했으니 이를 보시는게 더 이해가 쉬우시리라 생각됩니다!

 

첫번째 반복을 통하여 옷의 종류별 개수를 구할 수 있습니다.

 

그리고 이제 조합할 수 있는 개수를 구할 건데 첫번째 예제를 통해 예를 들어 보자면 headgear 2개, eyewear가 1개씩 존재하는 상황이고 이를 통해 만들어낼 수 있는 조합은

1. yellow_hat (headgear)
2. green_turban (headgear)
3. blue_sunglasses (eyewear)
4. yellow_hat (headgear) + blue_sunglasses (eyewear)
5. green_turban (headgear) + blue_sunglasses (eyewear)

위와 같습니다.

즉 headgear 개수를 x, eyewear 개수를 y라고 했을 때,

[x + y + xy]가 됩니다. 그리고 이는 다항식의 곱셈 공식에 의해 [((x + 1) * (y + 1)) - 1] 과 같습니다.

만약 x, y 뿐만 아니라 하나의 종류가 더 추가되어 z 까지 있다고 하면 정답은

[x + y + z + xy + xz + yz + xyz] 가 될것이며, 이는 역시 다항식의 곱셈 공식에 의해 [((x + 1) * (y + 1) * (z + 1)) - 1] 과 같습니다.

 

글을 작성하기 전에 '어떻게하면 좀 더 쉽게, 확실하게 이해를 시켜드릴 수 있을까' 하여 다른 분들은 어떻게 설명하고 있는가를 참고하는데, 이 문제를 '옷의 종류 개수를 구한뒤 그냥 이렇게저렇게 곱해주면 경우의 수가 구해지고 거기엔 아무것도 입지 않은 상태가 들어있어 1을 마지막에 빼준다' 라고 설명하는 분들이 많았고 왜 그렇게 되는지 저같은 경우 오히려 이해가 되지 않아 차라리 명확한 수학적 근거를 통해 말씀드리는 것이 좋을 것 같다고 판단하였습니다.

 

그리하여 구할 수 있는 공식에 의해 x + 1, y + 1, ... 을 계속해서 곱해주고 난 뒤, -1 을 해주는 것으로 문제를 해결할 수 있습니다.

 

JavaScript 결과

Python 결과

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.