[Programmers]#Level2_롤 케이크 자르기, set, map

 

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. map 컨테이너

[Basic C++] #38_map, 연관 컨테이너

C++ 표준라이브러리에서 제공하는 map 컨테이너는 지정된 형식의 키와 값을 한 쌍으로 레드-블랙 트리 자료구조에 저장하는 연관 컨테이너입니다. map 컨테이너는 중복을 허용하지 않고 내부적으로 정렬된 상태를 유지하며, 키 값을 기준으로 오름차순 정렬하는 것이 특징입니다. 

 

2. set 컨테이너

[Basic C++] #29_Set, STL 컨테이너

C++ 표준 라이브러리에서 제공하는 set 컨테이너는 지정된 형식의 키를 레드-블랙 트리 자료구조에 저장하는 연관 컨테이너입니다. set 컨테이너는 키를 기준으로 중복을 허용하지 않고 내부적으로 정렬된 상태를 유지하며, 키 값을 기준으로 오름차순 정렬하는 것이 특징입니다.

 

3. 민수의 롤 케이크는 map, 철수의 롤 케이크는 set

1. 먼저, 숫자의 가짓수를 키, 그 개수를 값으로 map 컨테이너에 저장합니다. 그리고, 우리는 이를 '민수'의 롤 케이크로 가정합니다.
2. 그리고, map 컨테이너가 내부적으로 '숫자의 가짓수'(키)를 기준으로 오름차순 정렬하는 것을 이용하여, 가장 적은 가짓수를 갖는 토핑부터 set에 추가해 줍니다. 그리고, 우리는 set 컨테이너를 '철수'의 롤케이크로 가정합니다.
3. 위 작업을 반복하며, map 컨테이너의 키의 갯수와 set 컨테이너의 키의 개수가 같다면, 정답을 카운트해줍니다.

 

---

 

#3. 코드

// #1. 첫 번째 코드, 시간 초과 실패

// #include <string>
// #include <vector>
// #include <set>
// using namespace std;

// int solution(vector<int> topping) {
//     int answer = 0;
//     // 철수 롤케이크의 토밍 가짓수
//     set<int> s1;

//     for(int i=0; i<(int)topping.size()-1; ++i)
//     {
//         // 철수 롤케이크에 현재 토핑 추가
//         s1.insert(topping[i]);
//         set<int> s2;
//         for(int j = i+1; j<(int)topping.size(); ++j)
//         {
//             s2.insert(topping[j]);
//         }

//         // 철수 롤케이크의 토핑 vs 민수 롤케이크의 토핑
//         if(s1.size() == s2.size())
//         {
//             answer++;
//         }
//     }

//     return answer;
// }

/*
    @문제 : 배열을 두 부분 배열로 분할했을때, 숫자의 가짓수가 동일한 모든 경우의 수
    @설명 
            1. 먼저, map을 통해 각 숫자의 가짓수 모두 세고, 이를 민수의 롤케이크로 가정하자
            2. 다음으로, 민수의 롤케이크를 왼쪽부터 야금 야금 철수한테 떼주며, map 과 set의 key 값의 개수를 비교하며 경우의 수를 센다.
*/
// #2. 두 번째 코드, 철수 롤케이크는 set + 민수 롤케이크는 map

#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

int solution(vector<int> topping) {

    int answer = 0;
    map<int,int> m_cake; // 민수 롤케이크
    set<int> c_cake; // 철수 롤케이크

    // #1. 민수(철수 동생) 롤케이크를 다먹는다!
    for(int i=0; i<(int)topping.size(); ++i)
    {
        // #1. 이미 있던 토핑이야, 응 늦었어~
        if(m_cake.find(topping[i]) != end(m_cake))
        {
            m_cake[topping[i]]++;
        }
        // #2. 처음 보는 토핑이야, 응 안늦었어~
        else
        {
            m_cake.insert({topping[i], 1});
        }
    }

    // #2. 철수가 민수 롤케이크를 왼쪽부터 하나씩 야금야금 뺏어온다!
    for(int i=0; i<(int)topping.size(); ++i)
    {
        // #1. 민수 롤케이크에 이 토핑은 하나 줄어들어~
        if(m_cake.find(topping[i]) != end(m_cake))
        {
            if(--m_cake[topping[i]] == 0)
            {
                // 어? 그러면 이 토핑은 민수 롤케이크에 없는데?
                m_cake.erase(topping[i]);
            }
        }
        // #2. 철수 롤케이크에 이 토핑을 추가해볼까~?
        c_cake.insert(topping[i]);

        // #3. 철수 롤케이크 토핑 가짓수 vs 민수 롤케이크 토핑 가짓수
        if(c_cake.size() == m_cake.size())
        {
            answer++;
        }
    }

    return answer;
}

 

---