[프로그래머스 롤케이크 자르기] c++ (풀이, 코드)

문제 링크

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

프로그래머스

 

문제

 

풀이, 코드

 

코드에 대해서는 조금 더 다듬을 수도 있다고 생각합니다.

 

알고리즘 1일 1커밋을 실천하기 위해서 어떻게든 자정 넘어가기 전에 빠르게 풀다보니 이렇게 된것 같습니다..ㅎ

 

그래도 일단 너무 깊게 생각 안하고 제가 생각한 구조에 대해서 말씀 드리겠습니다.

 

구조

1. 일단 뒷놈이 다 가진걸로 생각한다. (map에 토핑마다 +=1을 해줍니다.)

2. 반복문을 돌면서 앞놈이 하나씩 가져간다고 생각합니다.

    1) 뒷놈은 map에 대해서 -= 1, 앞놈은 map에 대해서 +=1을 합니다.

    2) 만약 뒷놈이 0이 된다는 것은 토핑자체가 사라지는 것이지 map.erase를 통해 토핑을 지웁니다.

3. 만약 둘의 map 사이즈가 같다면?(=토핑 가짓수가 같다면?) answer++을 해줍니다.

 

/*

공평하게 나눠 토핑

1 2 1 3 1 4 1 2 -> 나눴을때 결국 맛볼 수 있는 토핑의 가짓 수 공평하게 자르는 방법의 수

일단 한명이 다 차지한다고 생각하고 진행 그리고 하나씩 당기면서 갯수 카운팅

*/

#include <string>

#include <vector>

#include <map>

using namespace std;

int solution(vector<int> topping) {

    int answer = 0;

    map<int,int> second; //뒷놈

    map<int,int> first; // 앞놈

    for(int i = 0; i < topping.size();i++){

        second[topping[i]] += 1; //우선 뒷놈에 다 넣어버림

    }

    for(int i = 0; i < topping.size();i++){ //한칸씩 앞놈으로 가면서 갯수가 같으면 answer++함

        if(second.find(topping[i]) != second.end()){

            second[topping[i]] -= 1;

            first[topping[i]] += 1;

            if(second[topping[i]] == 0){ // 0이라는것은 없는거지 뒷놈 map지움

                second.erase(topping[i]);

            }

        }

        if(first.size() == second.size())

            answer++;

    }

    return answer;

}