의상

• 코딩테스트 연습 > 해시 > 의상

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

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

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

코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.

• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.

• 같은 이름을 가진 의상은 존재하지 않습니다.

• clothes의 모든 원소는 문자열로 이루어져 있습니다.

• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ‘_’ 로만 이루어져 있습니다.

방법

• 해시테이블

• 처음엔 조합을 이용하는 것으로 생각했는데

• 알고보니 모든 경우의 수를 구한 뒤에 다 안입는 경우만(-1)로 빼주면 된다.

• 역시 수학을 잘하고 센스가 있어야 문제풀때 편할 것…

Python

# input setting
problem_num = "의상"
import os, sys

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
with open(path) as f:
    clothes = [line.split() for line in f.read().splitlines()]

"""
solution 1   
1번에 모든 종류에 하나씩만 있는 경우가 시간 초과가 걸림   
collections.combination을 사용할 경우 주어진 의상 조합의 수가 많기 떄문에 모든 경우의 수를 구하는 것 자체가 상대적으로 비효율적임
방법의 수를 구하는 것이기 떄문에 조합의 경우들을 직접 구하는 것 보다 쉬운 접근방식이 필요
"""

from itertools import combinations


def solution(clothes):
    # hash table 만들기
    closet = {}
    for cloth, Type in clothes:
        if Type not in closet.keys():
            closet[Type] = set()
            closet[Type].add(cloth)
        closet[Type].add(cloth)

    result = 0
    for r in range(1, len(closet) + 1):
        for combo in combinations(closet.keys(), r):
            # 현재 조합에 대한 값들을 곱해서 더하기
            product = 1
            for key in combo:
                product *= len(closet[key])
            result += product

    return result

for문을 3번 돌면서 combination의 사실상 곱하기를 하면서 더하는 것이기 때문에 시간효율성 면에서 떨어지는 것으로 보인다.

"""
solution2
방법의 수만을 구하는 방법.
모든 의상 종류별로 각각을 선택하거나 선택하지 않는 경우를 마지막에 빼주는 방법
"""

from collections import defaultdict


def solution2(clothes):
    closet = defaultdict(int)

    # 의상 종류별로 개수 세기
    for cloth, kind in clothes:
        closet[kind] += 1

    result = 1
    for count in closet.values():
        # 해당 종류의 의상을 선택하지 않는 경우까지 고려하여 +1
        result *= count + 1

    # 모든 의상을 선택하지 않는 경우 하나를 뺌
    return result - 1

solution2(clothes)

5

Javascript

const fs = require('fs'); // Node.js의 파일 시스템 모듈을 불러옵니다.

const problemNum = '의상'; // 문제 번호
const path = `${__dirname}/txt/${problemNum}.txt`; // 파일 경로

fs.readFile(path, 'utf8', (err, data) => {
    if (err) {
        console.error('파일을 읽는 도중 오류가 발생했습니다.');
        return;
    }

    // 파일을 줄 단위로 나누고 공백을 기준으로 데이터를 분리합니다.
    const clothes = data.split('\n').map(line => line.split(' '));

    // 이후 clothes 배열을 사용하여 데이터 처리를 진행합니다.
    console.log(clothes);

    function solution(clothes) {
        var closet = {};

        for (var i = 0; clothes.length > i; i++) {
            // var cloth = clothes[i][0];
            var kind = clothes[i][1];
            closet[kind] = (closet[kind] || 0) + 1;
        }

        var result = 1;
        for (var kind in closet) {
            result *= closet[kind] + 1;
        }

        return result - 1;
    }

    console.log("answer : ",solution(clothes));
});

python은 자연스러운 것들이 자바스크립트에서는 표현이 조금씩 달라기지 때문에

하나의 파일 안에서 python, javascript를 동시에 사용하는 것은 어려워 보인다.