프로그래머스/해시/위장

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

 

풀이

- 스파이들은 매번 다른 옷으로 조합해서 입어야 함 (그냥 하나의 항목만 다르면 됨)

- 놀랍게도 최소 한 부위만 입으면 되므로, 티셔츠만 하나 입는 것도 가능함 :O.... 그게 스파이냐

- 서로 다른 옷 조합의 수를 return하도록 짜기

 

- Input은 이런 방식. ["crowmask", "face"]

- 'face' 키에 밸류로 리스트를 넣으면 되겠군

- 키 하나, 둘, 셋, ..., N개를 뽑아서 조합을 시도하면 되겠군

- 조합을 시도할 때 해당 항목에 리스트의 개수를 생각해서 넣으면 되겠군

 

C#

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {

    public int solution(string[,] clothes) {
        
        var answer = 0;
        var closet = new Dictionary<string, List<string>>();
        
        //옷장에 정리해두기
        for(int i=0; i<clothes.GetLength(0); i++)
        {
            if(!closet.ContainsKey(clothes[i, 1]))
                closet.Add(clothes[i, 1], new List<string>());
            
            closet[clothes[i, 1]].Add(clothes[i, 0]);
        }
        
        //최소 1개 이상의 종류를 뽑아서 입기
        for(int i=1; i<=closet.Keys.Count; i++)
        {
            var combination_of_types = new CombinationSet(closet.Keys.ToList(), i).result;
            var result = 1;
            
            foreach(var e in combination_of_types)
            {
                foreach(var type in e) {
                    result *= closet[type].Count;
                }
                
                answer += result;
                result = 1;
            }
        }

        return answer;
    }

    public class CombinationSet
    {
        public List<List<string>> result;
        private List<string> elements;
        
        public CombinationSet(List<string> elements, int count)
        {
            result = new List<List<string>>();
            this.elements = elements;
            
            get_combination(count, new List<string>(), 0);            
        }
        
        private void get_combination(int count, List<string> tmp, int index)
        {
            if(count == 0)
            {
                result.Add(new List<string>(tmp));
                return;
            }
            
            for(int i=index; i<elements.Count; i++)
            {
                tmp.Add(elements[i]);
                get_combination(count - 1, tmp, i+1);
                tmp.RemoveAt(tmp.Count - 1);
            }
        }
    }
}

 

결과

정확성 96.4/100

 

피드백

1번 테스트케이스에서만 시간 초과.

시간 초과는 극단적인 케이스에서 발생한다. 예를 들어, 30종류의 옷을 1가지씩 가지고 있으면 무한으로 조합을 돌리게 된다 (...)

 

다시 풀어본다.

 

---

풀이

- 매우 쉬워지는 방법이 있다. 각 파츠에 Naked 상태를 추가해보자. 이러면 그냥 순열이 되는 마법

- 그래도 전부 Naked일 수는 없으니 결과값에서 1만 빼준다.

 

using System;
using System.Collections.Generic;

public class Solution {

    public int solution(string[,] clothes) {
        
        var answer = 1;
        var closet = new Dictionary<string, List<string>>();
        
        //옷장에 정리해두기
        for(int i=0; i<clothes.GetLength(0); i++)
        {
            if(!closet.ContainsKey(clothes[i, 1]))
                closet.Add(clothes[i, 1], new List<string>());
            
            closet[clothes[i, 1]].Add(clothes[i, 0]);
        }
        
        //각 키에 Naked 상태 추가하기
        foreach(var type in closet.Keys){
            closet[type].Add("Naked");
        }
        
        //한 파츠씩 뽑아서 입기. 순열이 되어버렸다
        foreach(var type in closet.Keys){
            answer *= closet[type].Count;
        }
        
        //다 벗고 돌아다닐 순 없는걸
        return answer - 1;
       
    }

}

 

결과

정확성 100/100

 

피드백

사실 Dictionary도 <string, string>일 필요가 없다. 가짓수를 출력하는 것이지 데이터를 출력하는 것이 아니니까.

<string, int>로 해시를 만들면 충분하긴 한데, 굳이 그 정도로 바꿀 필요성은 느끼지 못함.