롤케이크 자르기

링크

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

문제

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

예를 들어, 롤케이크에 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 함수를 완성해주세요.

풀이

이 문제는 topping 배열을 어느 한 지점에서 잘라 반으로 만들었을 때, 양쪽의 배열의 원소들의 중복을 모두 제거했을 때 두 배열의 길이가 같도록 하는 지점의 수를 구하면 된다.

주의할 점은 topping의 기본적인 길이가 최대 백만이기 때문에 시간초과에 걸릴 가능성이 매우 높다.

function solution(topping) {
    let count = 0
    
    topping.forEach((el, idx) => {
        const front = topping.slice(0, idx + 1)
        const back = topping.slice(idx + 1)
        
        const setFront = new Set(front)
        const setBack = new Set(back)
        
        if(setFront.size === setBack.size)
            count++
    })
    
    return count
}

예를 들어 위와 같은 코드가 있다면 반복문을 한 번만 돌리는 것 같지만 실질적으로는 slice, Set을 만드는 행위도 반복과 같이 작동하기 때문에 백만이 중첩되면 시간초과에 걸릴 가능성이 매우 높다.

따라서 slice 과정을 없애고 중첩이 제거된 길이를 반복없이 진행할 수 있도록 코드를 고쳐야한다.

여기서는 배열 대신에 object 객체 2개를 통해 문제를 해결했다. object 객체를 통해서 중첩을 표현한다. 배열에 등장하는 원소를 키로 넣고 그 개수를 값에 넣어서 표현을 하였다.

topping 배열을 처음부터 끝까지 진행하며 객체에 해당 원소로 키가 없으면 키-값쌍을 생성하고, 키가 존재하면 값을 +1하여 원소의 개수를 중첩시켜준다. 또한 키-값쌍이 새로 생성될 때 길이를 나타내는 변수를 +1씩 증가하도록한다.

그 후에 topping 배열을 다시 순회하면서 똑같은 방법으로 객체를 생성하고 이미 만들어놓은 객체에서는 그 값을 -1씩 하며 topping의 원소가 하나 씩 넘어가는 모습을 구현한다. 이 과정에서 새로 만들어지는 개체의 길이도 계속 작성하고 이미 만들어진 객체에서 하나하나 삭제하며 값이 0이 되는 경우에 길이를 -1씩 진행하여 객체가 가지고 있는 중첩이 제거된 원소의 개수를 구하도록 한다.

매 반복마다 두 객체의 길이가 같다면 현재 자른 지점이 두 객체에서 중첩이 제거된 원소의 개수가 동일하다는 것이므로 반환할 값을 1씩 증가하도록 한다.

코드

// object 객체를 활용해서 topping 배열이 가지고 있는 전체 토핑을 back에 몰아넣고
// 키는 토핑 종류, 값을 토핑의 개수로 객체를 구성
// for문을 반복하며 back객체에서 front객체로 이동한다는 느낌으로 코드를 작성
// 값이 0이 되면 객체 내에서 삭제
// 키의 개수가 같은지를 확인하는 방식으로 코드를 작성
// 객체의 길이를 알기 위해서 object.keys가 결국 순회하기 때문에 상당히 오래 걸림 
function solution(topping) {
    let count = 0
    
    let front = new Object()
    let back = new Object()
    
    let frontLen = 0
    let backLen = 0
    
    // back 객체 생성
    topping.forEach(el => {
        if(Object.hasOwn(back, el)) {
            back[el] = back[el] + 1
        } else {
            back[el] = 1
            backLen++
        }
    })
    
    topping.forEach(el => {
        if(Object.hasOwn(front, el)) {
            front[el] = front[el] + 1
        } else {
            front[el] = 1
            frontLen++
        }
        back[el] = back[el] - 1
        
        if(back[el] === 0) {
            delete back[el]
            backLen--
        }
        
        if(frontLen === backLen) count++
    })
    
    return count
}