문제 132265. 롤케이크 자르기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크 위에는 여러가지 토핑들이 일렬로 올라가 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 양이 아닌 위에 올라간 토핑들의 종류가 동일한 것을 공평하다고 생각합니다. 

롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

입력

• 롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping

입력 제한

• 1 ≤ topping의 길이 ≤ 1,000,000
  
  • 1 ≤ topping의 원소 ≤ 10,000

입력 예제

// input
[1, 2, 1, 3, 1, 4, 1, 2]

// ans
2

 

풀이 방식

이 문제는 매우 쉽다. 롤케이크 전체에 올라가 있는 토핑 종류와 개수를 전부 구해놓은 다음, 다시 왼쪽부터 토핑 종류와 개수를 구해가면서 매번 종류가 동일한지 비교하면 된다.

롤케이크 전체에 올라가 있는 토핑 종류와 개수를 저장하는 자료구조를 m2, 왼쪽부터 토핑 종류와 개수를 구해가는 자료구조를 m1이라고 하였을 때, toppings를 순회하며 m1는 해당 토핑 종류의 개수를 더하고, m2는 개수를 뺀다. 이 때, m1과 m2의 종류가 동일하다면 토핑 종류가 동일하므로 정답을 1증가시킨다.

위의 반복 과정이 끝나면 정답이 나온다.

 

정답 코드 

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    map<int, int> m1;
    map<int, int> m2;
    
    for(int elem : topping){
        m2[elem]++;
    }
    
    int idx =0;
    for(int elem : topping){
        m1[elem]++;
        m2[elem]--;
        if(m2[elem] == 0) m2.erase(elem);
        
        if(m1.size() == m2.size()) answer++;
        //cout << idx << " " << m1.size() << " " << m2.size() << '\n';
        idx++;
    }
    return answer;
}