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

문제

프로그래머스

풀이

이 문제는 철수와 동생이 롤케이크를 자르는 모든 경우의 수를 고려하여, 두 사람의 롤케이크 조각에 있는 토핑의 종류 수가 동일한 경우의 수를 모두 찾는 것이다.

 

해결 과정

1. unordered_map을 사용하여 철수의 롤케이크 부분(leftCut)과 동생의 롤케이크 부분(rightCut)에 있는 각 토핑의 개수를 저장했다.
2. 초기 상태에서는 동생이 전체 롤케이크를 가지고 있다고 가정하고, 모든 토핑의 종류 수를 계산한다.
3. 그 다음, 철수가 왼쪽부터 한 조각씩 가져가는 것을 시뮬레이션하고, 철수가 전체 롤케이크를 가질 때까지 반복한다.
4. 각 단계에서 철수와 동생의 롤케이크에 있는 토핑의 종류 수를 비교하고 두 수가 같으면 answer를 1 증가시킨다.

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

using namespace std;

unordered_map<int,int> leftCut;
unordered_map<int,int> rightCut;

int solution(vector<int> topping) {
    int answer = 0, leftCount = 0, rightCount = 0;
    
    for(int i  = 0; i < topping.size(); i++)
        if(rightCut[topping[i]]++ == 0) rightCount ++;
    
    for(int i  = 0; i < topping.size() - 1; i++){
        if(leftCut[topping[i]]++ == 0) leftCount ++;
        if(--rightCut[topping[i]] == 0) rightCount --; 
        if(leftCount == rightCount) answer++;
    }
    
    return answer;
}