프로그래머스 - 의상

문제

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

종류이름

얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

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

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

 

제한 사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

 

입출력 예

clothes	return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]	3

 

예제 #1

headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

 

예제 #2

face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

 

풀이

문제가 가지는 특이사항은 다음과 같다.

• 스파이는 하루에 최소 한 개의 의상은 입는다.
• 리스트 타입으로 의상명과 해당 종류가 들어온다.

따라서 문제에서 요구하는 답은 해당 의상 종류별로 한개씩 또는 아무것도 입지 않는다고 할 때, 산출되는 총 경우의 수를 구하면 된다.

이 때 주의 사항으로, 스파이는 최소 1개의 의상은 입는다고 한다.

일단 문제를 읽어보면, 입력 값에서 "의상명"이 들어오는데, 이는 전혀 고려할 대상이 아니다.

따라서 우리는 들어오는 의상 "종류"별 갯수만 파악하면 된다.

이 때, 무슨 종류가 들어올지 모르겠지만, 들어온 의상의 기본 값은 1이다.

예를들어, 헤드기어에서 A와 B라는 의상이 들어왔다면, 헤드기어는 2개가 아닌, 3개로 취급해야 한다.

이유는 입지 않은 경우도 있으니까..

따라서 들어온 의상 종류별 갯수에 모두 1씩 더해 각 값을 곱해주고,

곱한 값에서 아무것도 입지 않은 경우 1개를 제외하면 정답이 된다.

ex.

상의 - A, B / 하의 - x, y

=> 상의 : "상의공백", A, B => 3개

=> 하의 : "하의공백", x, y => 3개

상의공백 + 하의공백 <-- 최소 하나는 입으므로 제외
상의공백 + x
상의공백 + y
A + 하의공백
A + x
A + y
B + 하의 공백
B + x
B + y

=> 총 3 * 3 - 1 => 8가지

 

소스 코드

int solution(vector<vector<string>> clothes)
{
  int answer = 1;

  unordered_map<string, int> mapClothes;

  // 의상 종류에 따른 개수 카운팅
  for (unsigned int i = 0; i < clothes.size(); i++)
  {
    if (mapClothes[clothes[i][1]] == 0)
      mapClothes[clothes[i][1]] = 2;
    else
      mapClothes[clothes[i][1]]++;
  }

  // 의상 종류에 따른 개수 카운팅
  unordered_map<string, int>::iterator iter;
  for (iter = mapClothes.begin(); iter != mapClothes.end(); iter++)
  {
    answer *= iter->second;
  }
  answer--;

  return answer;
}

파이썬을 공부 중이라.. 일부러 파이썬부터 짜보는데, 확실히 편의성은 파이썬이 대단한 것 같다..

def solution(clothes):
    answer = 1

    diction = {}

    for i in clothes :

        if i[1] in diction :

            diction[i[1]] += 1

        else :

            diction[i[1]] = 2    # 기본적인 공백(안입는 경우)

    for i in diction.values() :

        answer *= i

    answer -= 1 # 아무것도 안입는 경우 제외

    return answer

 

출처

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