코드굽는 타자기

Programmers[42578] - 위장[Level2] 본문

알고리즘/해시

Programmers[42578] - 위장[Level2]

bright-jun 2020. 4. 30. 03:05

링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

  • 조합 경우의 수

문제풀이

  • 조합 경우의 수 = 종류별 가능한경우 다 곱한 후, 아무것도 안고른 경우 빼기

문제코드

import java.util.HashMap;

public class Solution42578_위장 {

    public static int solution(String[][] clothes) {
//        {종류 , 종류개수}
        HashMap<String, Integer> hm = new HashMap<String, Integer>();

        for (String[] cloth : clothes) {
            if(hm.containsKey(cloth[1])){
                hm.put(cloth[1], hm.get(cloth[1])+1);
            }
            else {
                hm.put(cloth[1],1);
            }
        }

        int answer = 1;
        for (int val : hm.values()) {
            answer*=(val+1);
        }
        return answer-1;
    }

    public static void main(String[] args) {
        System.out.println(solution(new String[][] {
            {"yellow_hat", "headgear"},
            {"blue_sunglasses", "eyewear"},
            {"green_turban", "headgear"}
        }));
        System.out.println(solution(new String[][] {
            {"crow_mask", "face"},
            {"blue_sunglasses", "face"},
            {"smoky_makeup", "face"}
        }));
    }
}

아쉬운점

  • 사실 해쉬문제라 하기에는 종류의 개수가 5개뿐이라.. 굳이 해쉬 써야하나 싶기도 함.

    • 해쉬 구현에 의의를 두자.
  • Iterator 쓰는 법을 모름

  • Iterator<Integer> it = map.values().iterator();
           while(it.hasNext()) {
               answer *= it.next().intValue()+1;
           }

    이렇게 사용한다.

다른사람 풀이

  • dp로 풀 수 있음
  • 종류N선택안했을 경우 = NX, 종류N선택 = NO 로 표시한다
  • ~N은 N종류까지 선택했을 경우를 의미
1X 1O
~2X = 1X * 2X + 1O * 2X ~2O = 1X * 2O + 1O * 2O
~3X = ~2X * 3X + ~2O * 3X ~3O = ~2X * 3O + ~2O * 3O
... ...
~NX = ~(N-1)X * NX + ~(N-1)O * NX ~NO = ~(N-1)X * NO + ~(N-1)O * NO
  • ~N = ~NX + ~NO인데 여기서 1X2X...NX인 경우 1 빼주면 된다.
  • dp로는 생각도 못했는데 dp적 사고를 개발하기 좋은 접근법인 것 같다.
Comments