[알고리즘] 해쉬 위장(프로그래머스)

 

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

코딩테스트 연습 - 위장

해쉬 위장 문제

- 알고리즘의 부족함을 느껴 짬이 날 때마다 알고리즘 연습을 하기로 마음먹었다.

- 우선 한글로 된 프로그래머스를 통해 연습 중이다. 추후 영어 잘하고 실력이 향상되면 영문으로 된 다른 사이트의 문제들도 풀어볼 예정이다.

 

문제 설명

- 이미지로 대체한다.

- 간략히 설명하면 얼굴, 상의, 하의, 겉옷의 경우의 수를 구하는 것이다.

내 풀이 1번째

function solution(clothes) {
    const initCount = clothes.length;
    const convertToObjectClothes = clothes.reduce( (acc, cur) => {
        const value = cur[0]
        if(!acc[cur[1]]) {
            acc[cur[1]] = [];
        }
        acc[cur[1]].push(value)
        return acc
    },{})
    
    const count = !(Object.keys(convertToObjectClothes).length === 1) ? Object.keys(convertToObjectClothes).map( item => {
        return convertToObjectClothes[item].length
    }).reduce((acc, cur) => {
        return acc = acc * cur 
    },1) : 0
    
    return count + initCount;
}

- clohtes 매개변수를 각각 카테고리별 배열을 만들고 의상을 push 하여 객체로 만들었다.

- 이 객체를 통해 경우의 수를 만들었다.

- 하지만, 단순하게 얼굴, 상의, 하의가 있으면 얼굴 조합, 얼굴, 상의 조합, 얼굴, 상의, 하의 조합 이렇게 여러 조합이 가능한데 얼굴, 상의, 하의 조합과 1개씩 입고 있는 조합만 생각했다.

- 입출력 예는 통과했는데 실제 테스트에서 28점 정도 받아서 무엇이 문제인지 고민을 2일 했다.

- 질문을 봤나 갑자기 떠올랐나 기억이 안 났지만 문제를 파악했다. 3개의 카테고리가 있으면 2개의 카테고리 조합도 계산해야 된다는 사실을.....

- 해결을 하려고 다시 2일을 고민했지만 답이 나오질 않아 지인들에게 물어봐서 경우의 수라는 공식 같은걸 얻어냈다.

- 모든 카테고리별 조합을 할 때(꼭 카테고리별 1개씩 들어갈 경우),

예) 카테고리가 3개고 각 카테고리별 length가 2일 경우

얼굴	안경, 마스크
상의	반팔, 셔츠
하의	반바지, 긴바지

(안경, 마스크) * (반팔, 셔츠) * (반바지, 긴바지) - 1(전체 아무것도 안 고를 때)

2 * 2 * 2 - 1 = 7가지

 

- 모든 카테고리별 조합이 아닐 때(최대한 많은 경우의 수를 가지게!),

예) 카테고리가 3개고 각 카테고리별 length가 2일 경우

얼굴	안경, 마스크
상의	반팔, 셔츠
하의	반바지, 긴바지

(안경, 마스크 + 1) * (반팔, 셔츠 + 1) * (반바지, 긴바지 + 1) - 1(전체 아무것도 안 고를 때)

(2+1) * (2+1) * (2+1) - 1 = 26가지

내 최종 풀이

function solution(clothes) {
    const convertToObjectClothes = clothes.reduce( (acc, cur) => {
        const value = cur[0]
        if(!acc[cur[1]]) {
            acc[cur[1]] = [];
        }
        acc[cur[1]].push(value)
        return acc
    },{})
    
    return (Object.keys(convertToObjectClothes).map( item => {
        return convertToObjectClothes[item].length
    }).reduce((acc, cur) => {
        return acc = acc * (cur + 1) 
    },1)) - 1
}

 

- 이렇게 해서 테스트는 통과했다!

- 이번 알고리즘 풀이를 통해 느낀 점은 문제를 잘 읽어보고, 조건을 잘 체크하자!

- 그리고 마지막으로 경우의 수를 구하는 공식? 비법? 방법을 알아야 하니 수학 또는 알고리즘 이론은 공부하자!

 

다른 사람 풀이

function solution(clothes) {
    return Object.values(clothes.reduce((obj, t)=> {
        obj[t[1]] = obj[t[1]] ? obj[t[1]] + 1 : 1;
        return obj;
    } , {})).reduce((a,b)=> a*(b+1), 1)-1;    
}

- 다른 사람 최종 풀이를 보니 허탈했다. 단 몇 줄만으로 내가 며칠 동안 고민하던 게 저기 담겨 있으니... 더 열심히 해보자.