문제
프로그래머스에서 해시로 구분되어있는 문제이다.
의상-level2
문제설명
코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.
예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.
종류: 이름
얼굴: 동그란 안경, 검정 선글라스
상의: 파란색 티셔츠
하의: 청바지
겉옷: 긴 코트
코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 착용할 수 있는 조합의 개수를 return 하도록 solution 함수를 작성해주세요.
제한사항
clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
문제분석
코니가 입는 옷의 조합은 매일 달라져야하고 각 종류별로 착용할 수 있는 의상은 최대 1가지이다. 또한 매일 최소 한가지의 옷은 입어야 한다. 이때 서로다른 옷의 조합의 수를 구해야한다.
해시
해시
위의 링크에 정리해 놓았다.
해결방법
우선 조합의 수를 구하는 방법부터 생각을 하였는데 이 방법은 간단하다.
어떤 종류의 옷이 n개 있다면 그 종류의 옷을 입는 방법은 입지 않는것까지 포함하면 n+1개가 된다.
따라서 각 옷의 종류마다 종류의 개수+1을 모두 곱한 뒤 아무것도 입지않는경우 1을 뺴주면 조합의 수이다.
그 다음으로는 종류별로 나누는 것인데 이것은 간단하게 옷의 종류로 나누어 주면된다.
분류에는 map을 사용하여 key는 종류 value로는 벡터로 의상이름들을 삽입하여 해결하였다.
사용한 문법
해결방법이 생각보다 간단하서 알기만하고 써보지 않은 기능들을 몇개 써보았다.
iterator : 포인터를 일반화 한것이다.
auto : auto 초기화 식을 사용하여 해당 형식을 추론하도록 지시한다.
for each
for( auto i : arr ) 와 같이 사용하고 파이썬의 for i in arr과 유사하다.
코드
#include <string>
#include <vector>
#include<map>
using namespace std;
int solution(vector<vector<string>> clothes) {
int answer = 1;
map<string,vector<string>>m;
map<string,vector<string>>::iterator iter;
int size=clothes.size();
for(int i=0;i<size;i++)
{
iter=m.find(clothes[i][1]);
if(iter!=m.end())
{
iter->second.push_back(clothes[i][0]);
}
else{
m[clothes[i][1]].push_back(clothes[i][0]);
}
}
for(auto iter : m)
answer*=iter.second.size()+1;
return answer-1;
}
성공한 코드이고 여러 기능들을 위에서 말했던 3기능들을 사용하였는데 iterator 사용하여 구현을 해보려 했는데 처음 써보는 기능이라 컴파일과정에서 3-4번 막혔던것 빼고 나머지는 어렵지 않았다.
+
다 풀고 다른사람들의 풀이를 보니까 map의 value를 정수형으로 설정하고 해결을 많이했다.
그래서 map<string, int>로 바꾸고 다시 풀어 봤다.
#include <string>
#include<map>
using namespace std;
int solution(vector<vector<string>> clothes) {
int answer = 1;
map<string,int>m;
int size=clothes.size();
for(int i=0;i<size;i++) m[clothes[i][1]]+=1;
for(auto iter : m) answer*=iter.second+1;
return answer-1;
}
훨씬 간단해진다.
참고자료 : C언어로 쉽게 풀어쓴 자료구조
