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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    map<long, long> firstPiece;
    map<long, long> secondPiece;
    
    for(int i=0; i<topping.size(); i++){
        secondPiece[topping[i]]++;
    }
    
    int firstTopping = 0;
    int secondTopping = secondPiece.size();
    
    for(int i=0; i<topping.size(); i++){
        if(firstPiece[topping[i]] == 0){
            firstTopping++;
        }
        
        firstPiece[topping[i]]++;
        
        secondPiece[topping[i]]--;
        
        if(secondPiece[topping[i]] == 0){
            secondTopping--;
        }
        
        if(firstTopping == secondTopping){
            answer++;
        }
    }
    
    return answer;
}

---

📝 풀이

⭐ 참고 : 윈도우 슬라이딩 기법 ⭐

2024.07.25 - [코딩테스트/프로그래머스] - [프로그래머스] 할인 행사

[프로그래머스] 할인 행사

 

이 문제는 윈도우 슬라이딩 기법으로 풀 수 있습니다.

토핑을 key값으로 하고 같은 토핑일 경우 value값을 증가시키면 map의 size로 토핑 종류의 수를 알 수 있습니다.

첫 번째 조각은 아무 것도 없는 상태로, 두 번째 조각은 조각케이크 전체로 초기화합니다.

 

자르는 위치를 i라고 하고 첫 번째 조각에는 i의 토핑을 추가하고 두 번째 조각에는 i 토핑을 제거합니다.

첫 번째 조각에 토핑을 추가하기 전 존재 하지 않던 토핑이라면 토핑 종류 수를 증가시킵니다.

두 번째 조각에 토핑을 제거한 후 존재 하지 않는 토핑이 된다면 토핑 종류 수를 감소시킵니다.

두 조각의 토핑 종류 수가 같다면 answer을 증가시킵니다.

 

최종적으로 answer을 return합니다.