프로그래머스 (C/C++) 132265 : 롤케이크 자르기

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

프로그래머스

---

풀이

topping의 길이가 100만이라 주어진 배열을 여러 번 순회하는 방법은 안 될 것 같았다.

잘린 인덱스를 기준으로 앞 뒤의 값 차이가 얼마인지 계산해야 하므로 앞, 뒤 양 방향으로 순회해야 한다고 생각했다.

 

먼저 앞에서부터 순회하며 가장 마지막 인덱스에서 잘린 경우의 토핑의 가짓수(frontCnt)와 토핑 별 개수(frontSum[])를 센다.

다음으로는 뒤에서부터 순회하며 인덱스를 하나씩 옮기며 토핑 별 개수를 왼쪽(frontSum)은 감소, 오른쪽(backSum)은 증가시키며 해당 토핑이 오른쪽에 처음 나왔을 때(1)와 왼쪽에서 없어졌을 때(0)에 토핑의 가짓수를 각각 수정하며 같은 값이 나오는 경우 answer에 추가해줬다.

---

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0, size = topping.size();
    int frontSum[10001] = {0, }, frontCnt = 0;
    
    // 왼쪽에서부터 합 구하기
    for (int i = 0; i < size; i++) {
        int top = topping[i];
        frontSum[top]++;
        if (frontSum[top] == 1) frontCnt++;
    }
    
    // 오른쪽으로 한 칸씩 밀며 (왼쪽 토핑 개수) = (오른쪽 토핑 개수)인 지점 찾기
    int backSum[10001] = {0, }, backCnt = 0;
    for (int i = size - 1; i > 0; i--) {
        int top = topping[i];
        backSum[top]++; frontSum[top]--;
        
        if (frontSum[top] == 0) frontCnt--;
        if (backSum[top] == 1) backCnt++;
        
        if (frontCnt == backCnt)
            answer++;
    }
    return answer;
}