프로그래머스 위장

2019-11-15

1. 프로그래머스 위장문제

1.1. 컴퓨팅적 스킬

접근법

옷 종류 = KEY, 옷 이름= VALUE를 두고 문제를 해결해야 한다고 생각하였습니다.
#include<unordered_map> 헤더에 포함된 unordered_map<string,int> 형태로 사용하려고 하였습니다.
unordered와 map중 unordered 자료구조를 사용한 이유는 map은 balanced tree의 형태를 가지고 있고, unordered_map는 hash형태로 이루어져있기 때문에 성능차이의 이슈로 특별한 이유가 없는 한 unordered_map을 사용하려고 합니다.

주어진 파라미터 vector<vector<string>> clothes; 의 형태가 주어졌는데요. 헷갈리는 부분이 있어서 설명하고 넘어가겠습니다. vector<vector<string> 2차원 벡터는 2차원 배열과 형태가 같습니다.

그리고, 2차원 벡터에 값을 넣게 될경우 주의해야할 점이 한가지 있습니다. 직접 접근해서 벡터값을 넣지 못하게 되어있다는것입니다. clothes[0].push_back("yellow_hat") 처럼 값을 넣으려고 하였지만, Xcode에서 Invalid operands to binary expression 에러가 나타났습니다. 직접적으로 2차원벡터에 값을 바로 접근하기가 불가능한 모양입니다.

그래서 1차원 벡터를 생성시킨 후 값을 넣어준 다음, 2차원 벡터에 값이 들어간 벡터를 넣었습니다. 프로그래머스에서 테스트케이스로 바로 Input을 주기 때문에 이러한 과정이 필요없지만, 직접 소스코드를 Xcode에 작성하면서 디버깅도 해보는편이라 저런형식으로 넣어주게 되었습니다.

vector<vector<string>> clothes;
vector<string> v1;
vector<string> v2;
vector<string> v3;

v1.push_back("yellow_hat"); v1.push_back("headgear");
v2.push_back("blue_sunglasses"); v2.push_back("eyewear");
v3.push_back("green_turban"); v3.push_back("headgear");
clothes.push_back(v1);
clothes.push_back(v2);
clothes.push_back(v3);

1차원 행부분에서 열부분을 참고하시면 모든값들을 가져올 수 있겠습니다. 그리고, auto를 사용하셔서 값들을 가져올 수도 있습니다.

아래와 같은 3가지 형식으로 사용하시면 됩니다.

for(int i=0; i<clothes.size(); i++){
    m[clothes[i][1]]++;
}

or 
  
for(auto p : clothes){
    cout<< p.at(0);
  	cout<< p[0];
}

or
  
for(vector<string> s : clothes){
    cout<< s[0];
}

map에 있는 값들을 모두 확인하기 위해서는 iterator 를 사용하셔야 합니다. 사용하실 방식은 다음과 같습니다. map과 map::iterator를 선언시켜줍니다. 그리고 iter 변수를 사용해서 unordered_map에 있는 모든 값들을 탐색을 시작하게 됩니다. iter->first, iter->second로 참조하여 접근하게 되면 해당 맵의 <string,int>형태로 저장된 값을 가져올 수 있습니다.

unordered_map<string,int> m;
unordered_map<string,int>::iterator iter;
for(iter=m.begin(); iter != m.end(); iter++){
    answer *= (iter->second+1);
}

–

알고리즘

첫번째 테스트 케이스를 예시로 설명해보겠습니다. [headergear, eyewear] 의 두가지 종류가 있습니다. headgear를 입거나 안입는 경우 headgear = 2가지 경우, eyewear를 입거나 안입는 경우 1가지 경우입니다. 이것을 경우의 수로 적용시켜보겠습니다. (headgear +1)* (eyewear + 1)로 적용시키면 (2+1) * (1+1) = 6 - 1 = 5가지가 됩니다.
이때 +1을 왜 더하는거야? 라고 생각하실분이 있으실 것입니다. 그 이유는 의상을 입을까? 말까? 라는 경우를 고려해주어야하기 때문입니다. 그래서 +1을 해주게 되는것입니다.
마지막에 -1은 또 왜해주나요? 적어도 하나의 의상을 입어야하므로 모두 입지않는 경우의 수인 1가지 경우를 빼주어야 결국 모든 경우의 수의 조합이 나오게 될 것입니다.
모든 원소는 문자열로 이루어져있고, clothes는 [의상의 이름, 의상의 종류]의 형태를 가지고 있다. 따라서 해시 자료구조형을 사용해서 접근하면 된다. 처음에는 조합개념으로 dfs를 진행하려고 하였지만, 선택한 개수가 매번달라지는 경우때문에 dfs를 사용하지 않았습니다.

개인적으로 다시 풀면서 Java Hashmap을 이용한 풀이법도 올려놓았습니다.

1.2. 풀이

C++풀이

//
//  위장문제.cpp
//  algorithm-level-up
//
//  Created by kgh on 15/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

using namespace std;
int main(void){
    
    unordered_map<string,int> m;
    vector<vector<string>> clothes;
    vector<string> v1;
    vector<string> v2;
    vector<string> v3;
    
    v1.push_back("yellow_hat"); v1.push_back("headgear");
    v2.push_back("blue_sunglasses"); v2.push_back("eyewear");
    v3.push_back("green_turban"); v3.push_back("headgear");
    clothes.push_back(v1);
    clothes.push_back(v2);
    clothes.push_back(v3);
    
    for(int i=0; i<clothes.size(); i++){
        m[clothes[i][1]]++;
    }
    
    int answer = 1;
    
    unordered_map<string,int>::iterator iter;
    for(iter=m.begin(); iter != m.end(); iter++){
        answer *= (iter->second+1);
    }
    cout << answer-1;

    return 0;
}

Java 풀이

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        final int[] answer = {1};
        HashMap<String,Integer> hs = new HashMap<>();
        for(int i=0; i<clothes.length; i++){
            if(!hs.containsKey(clothes[i][1])){
                hs.put(clothes[i][1], 1);
            }else {
                int tmp = hs.get(clothes[i][1]);
                hs.put(clothes[i][1], tmp+1);
            }

        }
        hs.forEach((key, value) -> {
            System.out.print(value);
            answer[0] *= (value+1);
        });
        return answer[0]-1;
    }
}

AlgorithmProgrammers

1. 프로그래머스 위장문제

1.1. 컴퓨팅적 스킬

1.2. 풀이