프로그래머스 코딩테스트 연습 - 해시 - 위장 문제를 풀어보았다.
해시를 이용하는 문제였지만 사실상 나에겐 순열 조합 알고리즘에 대한 필요성을 깨닫게 해준 문제였다.
Programmers [해시] 위장
문제 목표
스파이가 보유한 옷의 종류와 옷들이 주어질 때 서로다른 옷 조합의 수를 return
제한사항
나의 풀이
손으로 어떠한 경우들이 있을지 그려보았고, 자연스레 옷 종류들의 조합들을 구한 뒤 옷 종류별로 보유한 옷 수를 곱해 모든 경우의 수를 count 할 계획으로 코드를 작성했다.
코드 실행 결과 테스트 1번에서 시간 초과가 발생하였고 질문하기에서 나의 풀이보다 훠얼씬 간단하고 명료한 풀이를 발견,,!!
스파이가 가진 옷 종류가 A,B,C 라면 스파이가 옷을 입는 경우는
1) A 만 입는 경우 (B, C 는 입지 않는 경우)
2) B 만 입는 경우 (A, C 는 입지 않는 경우)
3) C 만 입는 경우 (A, B 는 입지 않는 경우)
4) A, B 만 입는 경우 (C 는 입지 않는 경우)
...
와 같을 것이다.
즉, 무언가를 입지 않는 경우에 초점을 맞추어 생각하면 각 옷 종류 A,B,C 의 옷 수에 한가지를 더해서 생각할 수 있다 (투명옷이라 생각,,?ㅎ)
스파이가 옷을 입는 경우 의 수 = (A 옷 보유 수 + 1) (B 옷 보유 수 + 1) (C 옷 보유 수 + 1) - 1(아무것도 입지 않는 경우)
이러한 방식으로 생각하면 옷들이 조합되는 모든 경우를 따질 필요가 없고
종류별로 옷이 몇개 있는지만 해시를 이용해 count 하면 바로 정답을 구할 수 있었다..!
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int solution(vector<vector<string>> clothes) {
int answer = 1;
vector<string> kinds;
map<string, vector<string>> closet;
// closet - 각 옷 종류별로 옷 vector
// kinds - 옷 종류만 push
for(int i=0; i<clothes.size(); i++){
kinds.push_back(clothes[i][1]);
closet[clothes[i][1]].push_back(clothes[i][0]);
}
sort(kinds.begin(), kinds.end());
kinds.erase(unique(kinds.begin(), kinds.end()), kinds.end());
for (int i = 0; i <kinds.size() ; ++i) {
answer *= (closet[kinds[i]].size() + 1);
}
return answer-1;
}단순히 경우의 수를 따지면서도 분명 훨씬 효율적인 방법이 있을 것 같았는데,, 역시
순열 조합 알고리즘만 몇개 정도 더 풀어서 훈련이 필요할 듯 하다!
