[2025.03.10] 롤케이크 자르기

문제 설명

철수는 롤케이크를 두 조각으로 잘라서 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 왈려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.

 

예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다. 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다. 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)ㅇ르 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다. 공평하게 롤케이크를 자르는 방법은 여러가지일 수 있습니다. 위의 롤케이크 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다. 어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.

 

롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

• 1<=topping의 길이<=1,000,000
  • 1<=topping의 원소<=10,000

 

 

입출력 예

topping			result	설명
[1, 2, 1, 3, 1, 4, 1, 2]			2	롤케이크를 [1, 2, 1, 3], [1, 4, 1, 2] 또는 [1, 2, 1, 3, 1], [4, 1, 2]와 같이 자르면 철수와 동생은 각각 세 가지 토핑을 맛볼 수 있습니다. 이 경우 공평하게 롤케이크를 나누는 방법은 위의 두 가지만 존재합니다.
[1, 2, 3, 1, 4]			0	롤케이크를 공평하게 나눌 수 없습니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    int topping_size=topping.size();
    
    vector<int> from_front;
    vector<int> from_end;
    
    unordered_set<int> front_set;
    unordered_set<int> end_set;
    
    int count_front=0;
    int count_end=0;
    
    // 앞, 뒤로 조각마다 현재까지의 토핑의 종류 저장
    for(int i=0; i<topping_size; i++)
    {
        // 앞에서 부터 확인
        // 나온적 없던 토핑일 경우
        if(front_set.find(topping[i])==front_set.end())
        {
            front_set.insert(topping[i]); // set 업데이트
            count_front++; // count_front 1 증가
        }
        from_front.push_back(count_front); // 벡터에 현재까지 토핑 종류 저장
        
        // 뒤에서 부터 확인
        // 나온적 없던 토핑일 경우
        if(end_set.find(topping[topping_size-i-1])==end_set.end())
        {
            end_set.insert(topping[topping_size-i-1]); // set 업데이트
            count_end++; // count_end 1 증가
            
        }
        from_end.push_back(count_end); // 벡터에 현재까지 토핑 종류 저장
    }
    
    // 공평하게 자르는 방법의 수 구하기
    for(int i=0; i<topping_size; i++)
    {
        if(from_front[i]==from_end[topping_size-i-2]) // 토핑의 종류의 수가 같다면
        {
            answer++; // answer 1 증가
        }
    }
    
    return answer;
}

어떻게 문제를 풀어야 할지 고민하다가 이런 방법을 써보기로 하였다. 앞(왼)에서부터 한 조각씩 보면서 지금까지 토핑의 종류가 몇 가지 였는지 저장하고, 똑같이 뒤(오)에서부터 한 조각씩 보면서 지금까지 토핑의 종류가 몇 가지였는지 기록하는 것이다. 그리고 이 기록을 가지고 양쪽 모두 종류가 같은 경우를 찾는 것이다.

 

기록을 만들기 위해서는 for문을 이용하여 topping 전체를 순회해야 한다. 그리고 그 후에 할 일은 간단하다. 현재 토핑이 지금까지 나온적이 없다면 새로운 토핑의 종류가 추가된 것이니 토핑의 종류 수를 업데이트하고 벡터에 저장하면된다. 이미 나온적 있는 토핑이라면 토핑의 종류 수를 업데이트하지 않고 이전과 똑같은 종류 수를 벡터에 저장한다.

하지만 여기서 한가지 더 처리해 줘야 하는 일이 있다. vector에서 find 함수를 사용한다면 연산을 많이하게 되기 때문에 다른 방법으로 지금까지 나온적이 있는지 없는지를 확인해주어야한다. 그래서 vector만이 아니라 다른 자료구조를 들고 왔다. 바로 unordered_set이다. 중복없이 저장하고 탐색이 빠르기 때문에 사용해주었다. 그래서 새로운 종류의 토핑이 나타나면 unordered_set을 업데이트 해주는 과정도 하나 더 필요하게 되었다.

이 과정을 앞에서부터도 하고 뒤에서부터도 하면 된다.

 

마지막으로 공평하게 자르는 방법의 수를 구하기 위해 다시한번 반복문을 돌아준다. 위의 과정을 반복하면 이런 식으로 데이터가 저장될 것이다. 입출력 예 1을 예시로 들면 이렇다.

from_front : [1, 2, 2, 3, 3, 4, 4, 4]

from_end : [1, 2, 3, 3, 4, 4, 4, 4]

i가 0일 때부터 생각해보자. 앞에서 한 조각만 가져간다면 뒤에서는 7조각을 가져가야한다. 하지만 이건 조각으로 생각했을 때이고 인덱스로 생각하면 이렇다. 0번째 조각만 앞에서 가져간다면 뒤에서는 뒤에서부터 6번째 조각까지 가져가야한다. 즉 i가 0일 때는 뒤에서부터 조각을 자르는 사람은 i가 6인 것까지 봐야한다는 것이다. 그래서 이렇게 두 수를 비교하면 된다. 실제는 8조각이지만 index는 7까지 있기 때문에.

if(from_front[i]==from_end[topping_size-i-2])

이렇게 하다보면 from_front[3]과 from_end[8-3-2]가 같다는 것을 알 수 있다. 그리고 from_front[4]와 from_end[8-4-2]가 같다는 것을 알 수 있다. 8개의 조각 중 공평하게 자르는 방법은 각각 4, 4와 5, 3조각일 때라고 하였다. 결과와 일치한다. 이렇게 두 종류의 수가 같을 때만 answer 값을 업데이트하여 정답을 만들면된다. 공평하게 자르는 방법이 없다면 아무 처리가 이루어지지 않을 것이므로 자연스럽게 0이 반환될 것이다.

 

참고 사항

unordered_map은 Hash Table로 구현된 자료구조라 평균 O(1) 시간에 검색/삽입/삭제가 가능하다. 따라서 vector에서 find함수를 사용하는 것보다 unodered_map에서 find를 진행하는 것이 훨씬 더 빠르다.

비교 항목	vector.find()	unordered_set.find()
자료구조 유형	동적 배열(std::vector<T>)	해시 테이블(std::unordered_set<T>)
탐색 방식	선형 탐색(순차적으로 하나씩 비교)	해시 탐색(키를 해싱하여 직접 접근)
시간 복잡도	O(N)(최악의 경우)	O(1)(평균), O(N)(최악의 경우-해시 충돌 발생 시)
최적 성능	요소의 개수가 적을 때 빠름	요소의 개수가 많을 때 빠름
최악 성능	N이 커질수록 탐색 속도가 느려짐	해시 충돌이 많으면 성능 저하 기능(O(N))
중복 허용 여부	허용(중복된 요소 삽입 가능)	허용하지 않음(중복 요소 자동 제거)
정렬된 상태 유지	가능(삽입 순서를 유지)	불가능(내부적으로 정렬되지 않음)
메모리 사용량	낮음(배열 크기 만큼)	높음(해시 테이블을 유지하기 위한 추가 메모리 필요)
사용 예시	- 작은 데이터에서 특정 값 탐색 - 원소의 순서가 중요한 경우	- 빠른 중복 검사가 필요할 때 - 데이터 개수가 많을 때

 

 

오답 노트

처음엔 unordered_set을 사용하지 않고 vector만 이용해서 코드를 작성하였다. 하지만 vector에서 find 함수를 사용하니 최악의 경우 시간 복잡도가 O(N^2)가 되어 시간 초과 문제가 발생하였다. 그래서 다른 방법을 찾다 unordered_set을 사용해보기로 하였다. unordered_set을 사용하면 중복 확인이 평균 O(1)이므로, 전체 시간 복잡도를 O(N)으로 줄일 수 있다.

if(find(topping.begin(), topping.begin()+i, topping[i])!=topping.begin()+i)
{
    from_front.push_back(count_front);
}
else
{
    count_front++;
    from_front.push_back(count_front);
}

 

 

문제 링크

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

프로그래머스