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

문제 URL 위장

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이 문제에서 중요한 것은 2가지입니다.

 

1. 입력은 "옷, 파츠" 쌍의 2차원 배열입니다.
2. 옷의 이름은 1개입니다.

이 문제는 "해시 + 경우의 수"로 풀 수 있습니다. 무슨 말이냐, 첫 번째 입력을 보겠습니다.

 

입력 : [ ["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"] ]

 

이 들어온 입력에 대해서 { 파츠 : 옷의 개수 } 쌍으로 저장하는 해시를 만들어 줍니다.

 

입력을 통해 만들어지는 해시 : { "headgear" : 2, "eyewear" : 1 }

 

이 때, 각 파츠를 조합해서 만들 수 있는 경우의 수를 도입하면 됩니다. 경우의 수는 다음과 같은 수식이 성립합니다.

 

경우의 수  = ( 파츠 1의 옷의 개수 + 1 ) x ( 파츠 2의 옷의 개수 + 1 ) x .. x (파츠 N의 옷의 개수 + 1) - 1

 

즉 이 입력에 대한 결과는 3( "headgear" 파츠의 옷의 개수 2개 + 1) x 2 ("eyewear" 파츠의 옷의 개수 1개 + 1) - 1 = 5개가 됩니다.

구르미의 알고리즘 풀이

이전 절에서 파악한 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. clothes를 다음과 같이 순회 해서 해시를 만듭니다.
   1. 해시에서 "파츠"를 키로 저장하는지 찾습니다.
   2. "파츠"의 키가 없다면, 0을, 존재하면 "파츠"와 쌍으로 저장된 값을 불러옵니다.
   3. 옷의 개수를 1 증가시킨 후, 다시 해시에 저장합니다.
2. 만들어진 해시를 토대로, 각 파츠를 조합하는 경우의 수를 구합니다. 이는 다음과 같이 구하면 됩니다.
   1. answer의 초깃값은 1입니다.
   2. 해시를 순회하며 저장된 (키, 값) 쌍으로 된 엔트리를 가져옵니다.
   3. 값에 + 1을 더한 후, answer와 곱해줍니다.
   4. 순회를 마치면 answer에 1을 빼줍니다.

파이썬 코드는 다음과 같습니다. 파이썬 같은 경우, 유틸 함수가 언어에서 기본적으로 제공을 해주기 때문에, 보다 코드가 짧습니다. cpp와 비교해서 보시면 이해가 쉬울 것입니다.

 

def solution(clothes):
	# { 파츠 : 옷의 개수 } 저장하는 해시 생성
    d = dict()
    
    for _, body in clothes:
        d[body] = d.get(body, 0) + 1
    
    answer = 1
    # 경우의 수 알고리즘 적용
    for v in d.values():
        answer *= (v + 1)
    
    return answer-1

# main 함수
if __name__ == '__main__':
    clothes = [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]
    result = solution(clothes)
    print(result)

 

cpp 코드는 다음과 같습니다.

 

#include <string>
#include <vector>
#include <map>

#include <iostream>

using namespace std;

int solution(vector<vector<string>> clothes) {
	// {파츠 : 옷의 개수} 를 저장하는 해시 생성
    map<string, int> d;
    
    for (const auto & c : clothes) {
        const auto & body = c[1];
        d[body] = (d.find(body) == d.end() ? 0 : d[body]) + 1;
    }

    int answer = 1;
    // 경우의 수 알고리즘 적용
    for (const auto & set : d) {
        answer *= (set.second + 1);
    }

    return answer -1;
}

int main() {
    vector< vector<string>>clothes = {
        { "yellow_hat", "headgear" }, 
        { "blue_sunglasses", "eyewear" }, 
        { "green_turban", "headgear" }
    };
    auto result = solution(clothes)
    cout << result << endl;
    return 0;
}