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

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

프로그래머스

풀이

롤케이크의 토핑 정보 topping이 주어집니다. 임의의 위치를 잘랐을 때 두 사람이 가지는 토핑의 가짓수가 동일한 모든 경우를 찾고자 합니다.

 

unordered_map 자료구조를 사용해 topping 의 모든 정보를 기록해둡니다. 이때, um1, um2는 각각 두사람이 가지는 토핑의 종류와 갯수를 기록하기 위한 변수입니다.

 

topping을 topping.size()-1까지 순회하며 나오는 토핑을 um1에 추가하고, um2에서 빼줍니다. 이 때, 토핑을 빼주고 난후의 개수가 0이라면 토핑이 없는 것이므로 erase함수를 사용해 map 자료구조에서 key를 삭제해줍니다.

 

한 번 loop를 돌 때마다 map 자료구조의 size를 비교하며 토핑의 가지수가 같은 경우 answer++를 해주면 정답을 리턴할 수 있습니다. 

 

리뷰

topping의 범위가 1,000,000 이므로 2중 for loop를 사용한 완전탐색이 불가능한 문제입니다. 완전탐색이 필요하지만 시간제한이 걸릴 때 Prefix Sum 개념을 사용해 문제를 해결하는 방법을 고민해볼 수 있습니다. 

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

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
 
    unordered_map<int, int> um1;
    unordered_map<int, int> um2;
    // 전체 토핑 기록
    for (auto i : topping) {
        um2[i]++;
    }
    // um1과 um2의 크기가 같다면 토핑 가짓수가 같음
    // 단, 토핑의 개수가 0이 될 경우 삭제해줌
    for (int i=0; i<topping.size()-1; i++) {
        um1[topping[i]]++;
        um2[topping[i]]--;
        
        if (um2[topping[i]] == 0)
            um2.erase(topping[i]);
        
        if (um1.size() == um2.size()) answer++;
    }
    return answer;
}