프로그래머스 의상(lvl2)풀어보기

문제링크

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

프로그래머스

---

문제 핵심

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

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

---

알고리즘

경우의 수의 곱의 법칙

---

코드

 

 public static int solution(String[][] clothes) {

        int answer = 1;

        Map<String, Integer> clothesMap = new HashMap<>();

        for (String[] cloth : clothes) {

            clothesMap.put(cloth[1], clothesMap.getOrDefault(cloth[1], 0) + 1);

        }

        System.out.println(clothesMap);

        for (int count : clothesMap.values()) {

          answer*=(count+1);

        }

        answer-=1;

        System.out.println(answer);

        return answer;

    }

 

---

결과

---

gpt피드백

수학공식이여서 딱히 평가 받을게 없다

 

---

후기

청음에 dfs로 구현했다

1개가 시간초과가 난것이다

느낌이 수학공식을 알아야 될거같아서 gpt한테 물어봤다

아 수학공식을 모르는데 어케 풀겠나 그냥 dfs 복습했다고 생각한다

아래는 시간초과 코드 아마 모든 조합을 구하라 했으면 이게 정답일텐데

가지수만 구하라 이니 시간초과가 나게 설계되어있다

public static int solution(String[][] clothes) {

        int answer = 0;

        for (int i = 0; i < clothes.length; i++) {

            Map<String, String> wearing = new LinkedHashMap<>();

            wearing.put(clothes[i][1], clothes[i][0]);

            coount += 1;

            dsf(clothes, i, wearing);

        }

        answer = coount;

        System.out.println(answer);

        return answer;

    }

    public static void dsf(String[][] clothes, int index, Map<String, String> wearing) {

        System.out.println(wearing + "," + coount);

        for (int i = index + 1; i < clothes.length; i++) {

            if (wearing.containsKey(clothes[i][1])) {

                continue;

            }

            Map<String, String> nextWearing = new LinkedHashMap<>(wearing);

            nextWearing.put(clothes[i][1], clothes[i][0]);

            coount += 1;

            dsf(clothes, i, nextWearing);

        }

    }