D+24 D+25 스택 개념 + 롤케이크 js

스택개념 like 티슈

문제에서 최근 삽입한 데이터를 대상으로 연산해야 한다면 스택!

먼저 들어간 것이 마지막에 나오는 규칙 = 후입선출 또는 LIFO(Last In First Out)
이때 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop

ADT(abstract data type : 추상 자료형)

추상 자료형이란 인터페이스만 있고, 실제로 구현은 되지 않은 자료형.

스택의 ADT

1.push : 스택에 데이터 푸시
2.pop : 스택에서 최근 푸시한 데이터를 팝하고, 그 데이터 반환
3.isFull(가득 찼는지 확인)
스택에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean값을 반환.
가득 차 있다면 True, 아니면 false

4.isEmpty(비었는지 확인)
스택에 들어 있는 데이터가 하나도 없는지 확인해 boolean값을 반환.
데이터가 하나라도 있으면 false, 아니면 true

5.top(최근 삽입한 데이터 위치를 저장할 변수)
데이터 없는 기본값은 -1,
스택에서 최근에 푸시한 데이터 위치를 기록
6.ItemType data[maxsize] : 스택의 데이터를 관리하는 배열, 최대 maxsize개의 데이터를 관리

• 자료구조의 세부 동작을 공부하면 큰 도움이 됩니다.
  효율적인 알고리즘을 떠올릴 수 있게 해주기 때문!

스택 세부동작

push >
push(2)호출하면 내부적으로 1.isFull() 수행해 data배열에 데이터가 가득 찼는지 확인하고, 그렇지 않다면 top을 1만큼 증가시킨 후 top이 가리키는 위치 data[0]에 3을 추가.

pop >
내부적으로 isEmpty() 함수 우선 실행해 data 배열에 데이터가 없는 건 아닌지 확인하고, 데이터가 있다면 top을 1만큼 감소시키고 데이터 '3'을 반환.

문제

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

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

첫번째 내 풀이

function solution(topping) {
    // 원소개수 /2가능한지 ? 해당 개수/2만큼 카운트되는 배열 slice 경우 +=1 하기
    const atom = [...new Set(topping)];
    const atomLen = atom.length;
    let result =0;
    function atomCount(half) {
        let stack=[];
        let stackCount = 0;
        
        for (let n of half){
         if (!stack.includes(n)){ stack.push(n); stackCount +=1};
        }
        return stackCount
    }
         
    function splitArr(index) {
        let flag = false
        const aHalf = topping.slice(0, index);
        const bHalf = topping.slice(index);
        // 배열의 atom 개수 비교해서 같으면 +1
        return [aHalf,bHalf];
    }
    for(i=atomLen/2; i<topping.length-atomLen/2 +1; i++ ){
        const [aHalf,bHalf] = splitArr(i)
        
        const aCount = atomCount(aHalf)
        const bCount = atomCount(bHalf)
        if( aCount === bCount) {result+=1; }
    }
   
    return result;
}

다른사람 풀이 (1)

원소 하나하나를 돌면서, 해당 원소가 전체 개수 중 다 나왔을 경우 baseSet에서 제거하고
이 baseSet이 배열의 왼쪽 배열 중 원소개수, compareSet이 오른쪽 배열의 원소개수로 생각하면
baseSet:왼쪽배열 개수와 compareset:오른쪽 배열 개수가 같을때 answer 개수를 추가해주는 것이었다.

이제 topping의 topping의 원소개수 10,000개이고, topping의 길이가 1,000,000개로
시간초과를 해결하기 위해서, new Array를 만들어준 다음 해당 원소 개수를 counter해주는 부분이
필요했다.
topping 원소는 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;	// 토핑 length 1이면 종료 
    }
    
    topping.map(v=>{
        baseSet.add(v); // 중복되지 않도록 set에 넣어주기 
        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;
}

다른사람 풀이(2)

이게 더 시간이 적게 나온다.

function solution(topping) {
    // 형의 케이크, 토핑의 갯수를 세야한다.
    const cakeA = {}
    // 동생의 케이크, 토핑의 종류만 기록하면 된다.
    const cakeB = new Set()


    let answer = 0;
    // 형의 케이크에 올라간 토핑 종류
    let typeOfToppings = 0

    for (let i = 0; i < topping.length; i++) {        
        if (cakeA[topping[i]]) {
            cakeA[topping[i]]++
        } else {
            cakeA[topping[i]] = 1
            typeOfToppings++            
        }
    }


    // 케이크를 자르는 지점(index)를 정한다.
    // index에서 케이크를 자른 경우 토핑의 종류가 동등한지 비교한다.
    for (let i = 0; i < topping.length; i++) {
        cakeB.add(topping[i])
        cakeA[topping[i]]--

        // console.log(`${i}에서 케이크를 잘랐습니다.`)

        if (!cakeA[topping[i]]) {
            typeOfToppings--
            // console.log(`${topping[i]}가 형의 케이크에서 없어졌습니다.`)
        }
        if (cakeB.size === typeOfToppings) {
            // console.log(`${typeOfToppings}개로 토핑을 나누는 방법 추가+`)
            answer++
        }
    }

    return answer;
}