문제 설명
철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.
예를 들어, 롤케이크에 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
function solution(topping) {
var answer = 0;
let baseSet = new Set(); //토핑 종류
let compareSet = new Set(); // 비교 집합. 롤케이크를 자르면서 현재까지 사용된 토핑들의 집합
let counter = new Array(10001).fill(0); //토핑이 몇 개 있는지 저장할 배열. 토핑의 길이만큼 0으로 채워진 배열 생성. 인덱스가 0부터 시작하니까 모든 값이 인덱스에 매핑되도록 10001까지.
if(topping.length===1){
return answer; //토핑이 한 종류 밖에 없기 때문에 answer값 반환
}
topping.map(v=>{
baseSet.add(v);
counter[v]++;
}) //토핑 배열을 순회하며 각 토핑을 baseSet에 추가하고 해당 토핑의 개수를 카운트
topping.map(v=>{
if(counter[v]>=1){
counter[v]--;
} //토핑이 아직 남아있는 경우에는 해당 토핑의 수를 1감소. =해당 토핑을 사용했다는 것을 의미
if(counter[v]===0){
baseSet.delete(v);
} //현재 토핑의 개수가 0이 되었을 때(=해당 토핑을 더이상 사용할 수 없게 된다면) 해당 토핑을 baseSet에서 제거
compareSet.add(v); //현재 토핑을 추가
if(baseSet.size===compareSet.size){
answer++;
} //baseSet과 compareSet의 크기가 같아지면 (= 모든 토핑이 한 번 이상 선택됐을 때) 결과 반환
})
return answer;
}시간 초과 에러로 인해 참고한 다른 사람의 풀이.
여기서 다시 짚고 너머가는 해도해도 필자가 어려워하는 map()함수 사용
배열 내의 모든 요소에 대해 주어진 함수를 호출하고, 그 결과를 새로운 배열로 반환해준다. 기존 배열을 수정하지 않고, 각 요소를 변형하여 새로운 배열을 생성할 때 사용한다.
