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

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

 

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

프로그래머스

---

 

해결전략

 

 

 

 

---

 

처음 시도한 코드

 

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

map<int, int> myMap; // key: 토핑의 종류, value: 위치
int cnt; // 전체 토핑의 종류
vector<int> v;

int solution(vector<int> topping) {
    
    for(int i = 0; i < topping.size(); i++)
    {    
        // 이전에 등장한 토핑 종류인지 검색
        map<int, int>::iterator it = myMap.find(topping[i]);
        if (it != myMap.end())
        {
            it->second++;
            continue;
        }
                
        cnt++; // 이전에 등장하지 않은 종류의 토핑이면 ++
        myMap.insert({ topping[i], 1 });
        v.push_back(i); // 새로운 토핑이 등장하는 위치 기록
    }

    if (cnt % 2 == 1)
        return 0;
    else if (v.size() % 2 == 1)
        return 0;
    else
    {
        if (v[v.size() / 2] - v[v.size() / 2 - 1] <= 1) 
            return 0;

        return v[v.size() / 2] - v[v.size() / 2 - 1];
    }
}

 

 

---

 

정답 코드

 

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

map<int, int> myMap, newMap; // key: 토핑의 종류, value: 해당 토핑의 개수

int solution(vector<int> topping) {
    int answer = 0;
    
    for(int i = 0; i < topping.size(); i++)
    {    
        if(myMap.find(topping[i]) != myMap.end()) // 이전에 등장한 토핑 종류인지 검색
        {
            myMap[topping[i]]++; // 해당 토핑의 개수 증가
        }
        else
        {
            myMap.insert({ topping[i], 1 }); // 새로운 토핑 종류(key)와 해당 토핑의 개수(value) 기록
        }      
    }
        
    for (int i = 0; i < topping.size(); i++)
    {
        if(myMap.find(topping[i]) != myMap.end())
        {
            myMap[topping[i]]--; // 해당 토핑의 개수 감소

            if (myMap[topping[i]] == 0) 
                myMap.erase(topping[i]); // 0이 되면 myMap에서 지워준다.

            // 새로운 맵(newMap)에 토핑을 등록 또는 개수를 증가 시킨다.
            if (newMap.find(topping[i]) == newMap.end())
                newMap.insert({ topping[i], 1 });
            else
                newMap[topping[i]]++;
        }

        //** 만약 myMap.size() == newMap.size() 되는 경우가 없으면 answer이 증가되지 않아 초기 설정값인 0이 유지된다.
        //  myMap.size()는 계속해서 작아지고, newMap.size()는 계속해서 커진다.
        if (myMap.size() == newMap.size())
            answer++; // 옮겨지는 과정에서 myMap.size() == newMap.size()이 유지되는 상황에서는 계속 카운팅한다.  
    }
    
    return answer; 
}

int main()
{
    vector<int> testcase1 = { 1, 2, 1, 3, 1, 4, 1, 2 };
    vector<int> testcase2 = { 1, 2, 3, 1, 4 };

    cout<< solution(testcase3);

    return 0;
}

 

 

---

 

간결한 풀이

 

#include <vector>
#include <map>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;

    map<int, int> map1;
    map<int, int> map2;

    for (int& i : topping) {
        map1[i]++;
    }

    for (int i = 0; i < topping.size() - 1; i++) 
    {
        map1[topping[i]]--;
        map2[topping[i]]++;

        if (map1[topping[i]] == 0)
            map1.erase(topping[i]);

        if (map1.size() == map2.size())
            answer++;
    }

    return answer;
}