[C++] 의상 - 프로그래머스

문제

제한사항

입출력 및 예시

 

풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> category;

    // 옷 종류 별 분류
    for(vector<string> cloth : clothes)
    {
        string key = cloth.back();
        // 새 항목이라면
        if (category.find(key) == category.end())
        {
            // 새 항목 1 + 안입는다는 케이스 1 = 2
            category.insert(make_pair(key, 2));
        }
        // 기존에 있는 항목이라면
        else category[key]++;
    }

    int answer = 1;
    for (pair<string, int> cnt : category)
    {
        answer *= cnt.second;
    }
    // 모두 안입는 케이스 1 제외
    answer--;
    return answer;
}

 

풀이 설명

개인적으로 꽤나 직관적으로, 단순하게 해결했다고 생각하는 풀이이다.

 

처음엔 옷을 1개만 입는 경우부터 옷을 최대한 많이 입는 경우 수까지 나누어 구하려고 했으나, 카테고리(옷의 종류)의 갯수가 고정적이지 않고 입력값에 따라 변동될 수 있다는 것을 깨닫고 다시 접근했다.

 

해서 먼저 카테고리별로 종류를 나눠야 하기에 이에 적절한 자료구조인 'unordered_map'을 사용하고 key값에 카테고리 이름값인 string, value에 갯수를 나타낼 int 를 페어로 저장하도록 하였다.

 

첫번째 foreach 문에서는 최대한 순차적으로 접근하면서 경우의 수를 나누고자 하였다.

key값을 받고 category 에서 find를 진행하는데, find() 메서드는 해당 key를 나타내는 반복자(iterator)를 반환하기에 만약 값을 찾지 못했을 경우, 즉 find() 의 반환값이 자료구조의 가장 마지막인 category.end() 일 경우를 조건으로 걸었다.

 

이 경우 해당 key 에 대응하는 값을 찾지 못했다는 것이므로 신규 항목이라고 판단, key와 2를 페어로 맺어 category 에 추가해준다.

여기서 일반적인 값인 1이 아니라 2를 추가한 이유로는 주석에도 달아놨듯이 지금 반복 진행 중인 옷 갯수 1과, 이 key값의 옷 종류를 아예 입지 않는다는 경우까지 포함하여 2를 추가해줬다.

 

만약 find 가 성공될 경우, 이미 추가된 카테고리라고 판단하여 해당 key값의 value에만 ++을 진행해준다.

 

여기까지 진행되면 입력값 clothes 에 대한 카테고리 별 갯수 정리가 끝난 셈이다.

이후에는 경우의 수를 구해주기만 하면 되는데, 경우의 수 자체는 간단하게 '카테고리 별 가짓수의 곱' 으로 구할 수 있다.

 

다만 한가지 경우는 예외처리를 해줘야 하는데 바로 모든 종류에 대해 입지 않는다는 케이스이다.

category 항목에 value를 설정해줄 때, 입지 않는다는 선택지까지 포함하여 2로 초기화를 해주었기에 단순히 모든 가짓수의 곱만 구하게 될 경우 모든 종류의 옷에 대해 입지 않는다 라는 선택지까지 포함하게 된다.

하지만 문제에서 최소한 한가지의 옷은 입어야 한다 라고 명시되어 있기 때문에 해당 경우만 제외하는 'answer--'를 진행해주었다.

 

다른 사람 풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

    unordered_map <string, int> attributes;
    for(int i = 0; i < clothes.size(); i++)
        attributes[clothes[i][1]]++;
    for(auto it = attributes.begin(); it != attributes.end(); it++)
        answer *= (it->second+1);
    answer--;

    return answer;
}

 

프로그래머스 내에서 가장 많은 좋아요 수를 받은 풀이이다.

같은 unordered_map 자료구조와, 카테고리 별 가짓수의 곱이라는 정답 도출 과정 또한 동일하나 최적화와 처리 속도 부분에서 더 뛰어나다고 생각된다.

 

하나씩 차이점을 살펴보자면 반복문부터가 있다.

내가 작성한 코드의 반복문은

  for(vector<string> cloth : clothes)

으로 foreach 문을 진행하면서 clothes 에 대해 복사과정이 진행되는데, 이는 추가적인 메모리를 사용하게 되면서 최적화 쪽에서 아쉬움을 가질 수 있다.

반면에 다른 사람의 풀이에서는 for문으로 작성해 복사 과정이 없이 참조만으로 진행되어 더 효율적이라고 볼 수 있겠다.

만약 내 경우처럼 foreach 문을 사용한다면 const&를 사용해주는게 좋은 방법인데 이 부분에서 다소 아쉬움이 있다.

for(const vector<string>& cloth : clothes)

이 반복문에 대한 아쉬움은 두번째 반복문에서도 동일하다.

 

두번째 차이점으로는 category/attributes 에 대한 초기화 과정이다.

여기서는 unordered_map 에 대한 이해도 차이가 드러나는 부분인데, 나는 value값을 지정해주지 않고 초기화를 하게 될 경우 쓰레기값으로 초기화되어 ++을 진행해도 문제가 발생할 것이라고 생각되었다.

결과적으로 if문의 find 이후 else 쪽에서 operator[]를 한번 더 사용하게 되면서 기존 항목에 대한 과정이라면 탐색을 2번 진행하게 되는 비효율적인 로직이 만들어졌다.

 

이에 다른 사람의 풀이에서는

attributes[clothes[i][1]]++;

다음과 같이 clothes[i][1] 을 통해 옷의 카테고리를 저장한 두번째 string을 직접적으로 attributes의 key값으로 사용하였고, operator[] 를 곧바로 이어서 ++로 마무리하였다.

이 방법은 특정 key에 대해 새로운 key값일 경우 value가 int의 기본값인 0으로 초기화 된다는 점을 효율적으로 이용한 방법으로 신규 항목일지라 하더라도 {clothes[i][1], 1} 로 저장될 수 있도록 진행한 것이다.

 

세번째 차이점이지만 연산 자체에는 큰 차이가 없다고 생각되는 부분으로, 정답을 도출하는 과정인

answer *= cnt.second;

answer *= (it->second+1);

해당 내용에 대한 부분이다.

내 경우에는 make_pair 과정에서 처음부터 2로 초기화하여 해당 종류의 옷을 입지 않는 경우의 수를 추가하였기에 cnt.second를 곱하기만 하면 됐지만, 다른 사람의 풀이에서는 1로 초기화를 진행하였기에 입지 않는 경우의 수가 포함되어 있지 않다.

그 이유로 answer 의 연산 과정에서 second+1 을 진행해 입지 않는다는 경우의 수를 후반에 추가해준 모습이다.

 

 

문제에 접근하면서 어떤 자료구조를 선택하느냐에 따라 얼마나 효율적일 수 있냐에 차이점을 보인다는 점에서, 자료구조 선택의 중요성을 더 체감하게 된 계기이다.

추후에는 unordered_map 과 map 의 각 특성과 차이점 등에 대해서 알아보고자 한다.