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

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

프로그래머스

 

풀이 방법

롤케이크를 자르는 기준으로

왼쪽과 오른쪽의 상태를 map을 통해 관리할 것이다.

map의 키와 값은 <토핑의 종류, 해당 토핑의 개수> 형태이다.

 

 

먼저 topping 배열에 있는 토핑들을 모두 오른쪽에 존재한다고 생각하고

right_map에 모두 담는다. 이때 존재 여부에따라 연산은 다르다.

이미 존재하는 토핑이라면 +1, 존재하지 않는다면 1로 초기화 시킨다.

 

그리고 topping 배열을 돌며 left_map에 담는 과정을 거친다.

해당 토핑을 left_map에 담았을때 right_map에 해당 토핑의 개수는 1개가 줄어든다. 왜냐 왼쪽으로 옮겨갔기 때문.

 

이렇게 왼쪽에서 오른쪽으로 topping 배열을 돌며 left_map에 넣어주며

left_map의 크기와 right_map의 크기를 비교해주면

롤케이크를 잘랐을때 왼쪽 오른쪽 종류의 비교연산을 빠르게 수행할 수 있다.

 

 

전체 코드

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

int solution(vector<int> topping) {
    int answer = 0;
    map<int,int> left_m;
    map<int,int> right_m;
    
    //right_m에 숫자별로 몇개 존재하는지 추가
    for(int i=0; i<topping.size(); i++) {
        if(right_m.find(topping[i])!=right_m.end()) // 이미 존재한다면
            right_m[topping[i]]++; // 개수 +1 해줌
        else // 존재하지 않는다면
            right_m.insert({topping[i],1}); // 1개로 초기화
    }
    
    // left_m으로 옮기는 과정
    for(int i=0; i<topping.size(); i++) {
        if(right_m.find(topping[i])!=right_m.end()) { // right_m에 존재하는 숫자라면
            right_m[topping[i]]--; // right_m에 해당 숫자 개수 -1
            if(right_m[topping[i]]==0) // -1 했더니 0이라면 숫자가 존재하지 않는것임
                right_m.erase(topping[i]); // right_m에서 제거
            
            if(left_m.find(topping[i])==left_m.end()) // left_m에 옮기려했더니 left_m에 존재하지 않는 숫자임
                left_m.insert({topping[i],1}); // 1개로 초기화
            else
                left_m[topping[i]]++; // 개수 +1 해줌
        }
        
        
        if(left_m.size()==right_m.size()) // 하나 옮기는 과정 거쳤더니 left, right에 든 숫자의 종류가 동일하다면
            answer++;
    }
    
    return answer;
}