[프로그래머스][C++] 롤케이크 자르기

롤케이크 자르기

문제 링크

롤케이크 자르기

분석

배열의 각 원소는 토핑의 종류를 의미합니다.

형과 동생이 공평하게 나누기 위해서는 토핑의 종류 수가 같아야합니다.

롤케이크는 한번만 자를 수 있습니다.

롤케이크를 동생이 전부 가졌다고 가정한 상태에서 예시를 들어보겠습니다.
이때, 형인 철수가 토핑을 하나씩 가져가면서 동생의 토핑의 개수를 줄여 개수를 비교해봅니다.
만약 형과 동생의 토핑 개수가 같아졌다면 롤케이크를 공평하게 자르는 방법 중 한 가지입니다.

[1, 2, 1, 3, 1, 4, 1, 2]를 예시로 다음과 같습니다.

1. [1, 2, 1, 3, 1, 4, 1, 2]
2. [1, 2, 1, 3, 1, 4, 1, 2]
3. [1, 2, 1, 3, 1, 4, 1, 2]
4. [1, 2, 1, 3, 1, 4, 1, 2]
5. [1, 2, 1, 3, 1, 4, 1, 2]
6. [1, 2, 1, 3, 1, 4, 1, 2]
7. [1, 2, 1, 3, 1, 4, 1, 2]
8. [1, 2, 1, 3, 1, 4, 1, 2]
9. [1, 2, 1, 3, 1, 4, 1, 2]

풀이

#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    unordered_map<int, int> rollCake;   // 롤케이크의 토핑 종류와 개수 관리
    unordered_map<int, int> cheolSoo;   // 철수가 가진 토핑 종류와 개수 관리
    
    // 롤케이크의 토핑 종류와 개수 세기
    for (int e : topping)
    {
        ++rollCake[e];
    }
    
    // 모든 토핑 순회
    for (int i = 0; i < topping.size(); ++i)
    {
        // 롤케이크에서 현재 토핑의 개수 감소
        --rollCake[topping[i]];
        // 철수가 현재 종류의 토핑을 1개 가져감
        ++cheolSoo[topping[i]];
        
        // 롤케이크에서 현재 토핑의 개수가 없는 경우
        if (rollCake[topping[i]] <= 0)
        {
            rollCake.erase(topping[i]);
        }
        
        // 롤케이크에 남은 토핑 종류와 철수가 가진 토핑 종류가 같은 경우
        if (rollCake.size() == cheolSoo.size())
        {
            ++answer;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• rollCake를 초기화하는 반복문 $O(n)$
• topping를 순회하는 반복문 $O(n)$
• $O(n + n)$

공간 복잡도는 $O(n)$입니다.

• rollCake를 초기화 할 때 n개의 서로 다른 토핑의 종류가 존재하는 경우 $O(n)$
• cheolSoo 철수가 모든 토핑을 가져간 경우 $O(n)$
• $O(n + n)$

테스트 1 〉 통과 (0.61ms, 4.22MB)
테스트 2 〉 통과 (6.72ms, 7.35MB)
테스트 3 〉 통과 (3.32ms, 6.37MB)
테스트 4 〉 통과 (3.29ms, 6.2MB)
테스트 5 〉 통과 (33.09ms, 34.6MB)
테스트 6 〉 통과 (58.33ms, 37.5MB)
테스트 7 〉 통과 (36.47ms, 37.5MB)
테스트 8 〉 통과 (61.44ms, 37.4MB)
테스트 9 〉 통과 (35.92ms, 37.4MB)
테스트 10 〉 통과 (36.56ms, 37.5MB)
테스트 11 〉 통과 (3.32ms, 6.29MB)
테스트 12 〉 통과 (2.10ms, 4.36MB)
테스트 13 〉 통과 (37.07ms, 37.5MB)
테스트 14 〉 통과 (49.38ms, 36.7MB)
테스트 15 〉 통과 (42.23ms, 37.1MB)
테스트 16 〉 통과 (62.01ms, 36.7MB)
테스트 17 〉 통과 (60.87ms, 36.7MB)
테스트 18 〉 통과 (50.24ms, 36.8MB)
테스트 19 〉 통과 (59.65ms, 36.7MB)
테스트 20 〉 통과 (40.34ms, 37.2MB)