1주차 프로그래머스 - 의상(Lv2)

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

프로그래머스

   : 문제의 내용은 프로그래머스 문제를 참고해주세요

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String,Integer> map = new HashMap<>();

        for(int i = 0; i < clothes.length; i++){
            String clotheType = clothes[i][1];
            map.put(clotheType, map.getOrDefault(clotheType,0) + 1);
        }

        for(String key: map.keySet()){
            int typeCount = map.get(key);

            answer *= (typeCount + 1);
        }

        return answer - 1;
    }
}

문제 포인트

   1) ... 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.( = 같은 종류의 의상을 입으면 안됨)

   2) 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우... 

       (= 일부 조합에서 같은 의상이 보이더라도 다른 종류의 의상과 함께라면 괜찮음)

   3) 코니는 하루에 최소 한 개의 의상은 입습니다.(= 의상 하나만 입을 수 있음)

 

변수들의 범위

   1) 1 <= 코니가 가진 의상수(clothes) <= 30

   2) 1 <= 모든 문자열의 길이 <= 20 

 

시간 복잡도

  : 2N => O(N)

    * for한번에 최대 30이라 잡아도 60번 정도의 반복  

 

알고리즘에서 사용된 관련 메서드

  - HashMap.KeySet 내부 작동 원리 확인:

 https://mydeveloptrace.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%9C

 

테스트 케이스

  - 의상 종류: a, b     

  - 의상 이름: a1, a2, b1

  - 의상 종류의 갯수: A, B

     *A=2(a1, a2), B=1(b1)

  - 조합 가능한 모든 의상의 수: a1, a2, b1, a1b1, a2b1(5개)

 

  - 모든 의상 종류를 나타내는 식: (A + 1)(B + 1) - 1 = AB + A + B + 1 - 1

     * AB에 해당하는 경우: a1b1, a2b1 (2개)

       왜 A x B을 했는지?

            2       x     1         = 2

          a1                        = a1b1

                    x     b1

          a2                       = a2b1

          : ... 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.( = 같은 종류의 의상을 입으면 안됨)

             > 의상의 종류가 같은 경우: a1a2 (x)

          : 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우...

            (= 일부 조합에서 같은 의상이 보이더라도 다른 종류의 의상과 함께라면 괜찮음)

             > 조합별로 의상의 종류가 다른 경우: a1b1, a2b1 (O)

     * A에 해당하는 경우: a1, a2 (2개)       * B에 해당하는 경우: b1 (1개)

          : 코니는 하루에 최소 한 개의 의상은 입습니다.(= 의상 하나만 입을 수 있음 )

     * 1은 왜 더하고 뺐느냐?

          : 위의 AB, A, B의 경우를 모두 보기 위해서 임시적으로 추가됨