[Programmers] Lv2. 롤케이크 자르기 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

철수와 동생의 각 토핑 종류 수만 같으면 되기에, 중복이 되지 않는 자료구조가 필요합니다. 데이터의 개수가 최대 1,000,000개이기 때문에 검색, 삽입, 삭제에 좋은 해시(Hash)를 쓰기로 했습니다. Key-value 구조인 unordered_map과 Key 구조인 unordered_set을 사용하였습니다.

 

전략은 다음과 같습니다.

1. 저는 처음에 철수에겐 한 조각도 없고, 동생이 모든 케이크 조각을 가지고 있는 상태로 출발합니다.
   • topping을 순회하며, 각 토핑의 개수 카운트하여 저장 (unordered_map) \( \rightarrow \) 동생 꺼
2. 다시 topping을 순회하며, 철수에게 한 조각씩 동생이 양보해줍니다.
   • 철수는 토핑의 개수는 필요 없고, 종류 정보만 있으면 되기에 unordered_set을 사용
   • 동생이 철수에게 한 조각 양보했으면, 동생 꺼에서 해당 토핑 개수 한 조각 감소
     
     • 해당 토핑을 모두 양보하여 0개라면, key 삭제
   • 철수의 토핑 개수(unordered_set.size())와 동생의 토핑 개수(unordered_map.size())가 같으면 answer + 1

 

✏️소스 코드 및 결과

#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    unordered_map<int, int> youngerBrotherToppings;
    youngerBrotherToppings.reserve(topping.size());

    for (const auto i : topping)
        youngerBrotherToppings[i]++;

    unordered_set<int> olderBrotherToppings;
    olderBrotherToppings.reserve(topping.size());

    for (int i = 0; i < topping.size(); i++) {
        olderBrotherToppings.insert(topping[i]);
        auto toppingIt = youngerBrotherToppings.find(topping[i]);

        if (toppingIt == youngerBrotherToppings.end())
            continue;

        if (toppingIt->second > 0) {
            toppingIt->second--;

            if(toppingIt->second == 0)
                youngerBrotherToppings.erase(topping[i]);
        }

        if (olderBrotherToppings.size() == youngerBrotherToppings.size())
            answer++;
    }

    return answer;
}

 

제출 결과