[DAY 13] Equal Stacks @

You have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times.

Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of the three stacks until they're all the same height, then print the height. The removals must be performed in such a way as to maximize the height.

 

Equal Stacks | HackerRank

 

풀이

function equalStacks(h1, h2, h3) {
    let stacks = [h1, h2, h3];
    let temp = [];
    let result = 0;

    for(let i = 0; i < stacks.length; i++) {
        let sum = 0;
        for(let j = stacks[i].length - 1; j >= 0; j--) {
            sum += stacks[i][j];
            temp.push(sum);
        }
        stacks[i] = temp.reverse();
        temp = [];
    }
    stacks.sort(function(a,b) {
        return a.length - b.length;
    });
    for(let i = 0; i < stacks[0].length; i++) {
        let num = stacks[0][i];
        if(stacks[1].includes(num) && stacks[2].includes(num)) {
            result = num;
            break;
        }
    }
    return result;
}

1. 파라미터를 하나의 배열에 넣어줌. 기본 결과값은 0으로 처리

2. for문을 돌며 Stack높이 누적값을 임시 배열에 넣어줌.

3. 임시배열을 reverse()로 뒤집고, 원래 배열과 대치시킴. 다음 배열을 위해 temp는 다시 빈배열로..

4. stacks 배열을 정렬함(제일 짧은 높이를 찾기 위해) → 제일 첫번째 오는 배열이 제일 짧은 배열

5. 첫번째 배열을 돌면서 숫자를 꺼내서 다른 두 배열에도 그 값이 있으면 결과를 그 값으로 처리하고 for문을 끝냄(제일 큰 높이만 반환하면 되므로. 앞쪽 큰 수부터 찾음)

6. 결과를 반환함(없으면 0 반환, 있으면 값 반환

 

사실 스택이라는 것을 무시하고, 알고리즘을 풀음..핳.. 값을 하나씩 안빼고 그냥 includes를 이용했음

근데 자꾸만 Abort Called 에러가 뜨는 케이스들이 몇개 생김.. 근데 다른 사람들 코드도 다 그러네?

 

 

다른 사람의 풀이 1

function equalStacks(h1, h2, h3) {
    const sum = (arr)=>{
        return arr.reduce((sum, value) => sum + value, 0)
    }

   let sum1 = sum(h1);
   let sum2 = sum(h2);
   let sum3 = sum(h3);
   let min = Math.min(sum1,sum2,sum3); 
    
   while(true){
       if(sum1>min){
           sum1 -= h1.shift();
       }
       if(sum2>min){
           sum2 -= h2.shift();
       }
       if(sum3>min){
           sum3 -= h3.shift();
       }
       
       if(sum1 === sum2 && sum2 === sum3){
          return min; 
       }
       min = Math.min(sum1,sum2,sum3);
   }
}

1. sum이라는 함수를 만들어서 누적값을 계산하도록 함

2. 세 개의 파라미터를 sum함수에 넣어 각 배열의 합계를 구함

3. 그 중에 제일 최소값을 구함

4. While 문을 돌면서 최소값(min)과 각 배열값 합계를 비교, 배열값 합계가 크면 합계에서 배열의 값을 뺌* → 반복

5. 만약 합계 1, 2,3 이 같으면 최소값 반환

6. 최소값은 합계 1, 2, 3 중 가장 작은 값으로 갱신해줌

 

이 사람은 정말 stack처럼 top값을 빼가면서 계산하는 방식으로 결과를 구함. 

 

*shift() 함수는 가장 첫번째 값을 제거하고, 그 값을 반환함

 

 

다른 사람의 풀이 2

function equalStacks(h1, h2, h3) {
	let sums = [];
    let stacks = [h1, h2, h3];
    for (let i = 0; i < stacks.length; i++) {
        sums.push(stacks[i].reduce(function(acc, val) { return acc + val; }));
    }
    
    let found;
    let height = 1;
    while (height > 0) {
        found = false;
        height = Math.min.apply(null, sums);
        for (let i = 0; i < stacks.length; i++) {
            if (stacks[i].length > 0 && height < sums[i]) {
                sums[i] -= stacks[i].shift();
                found = true;
            }
        }
        
        if (!found) {
            break;
        }
    }
    
    return height;
}

1. stacks 배열에 파라미터를 다 넣어주고, for문을 돌면서 각 배열의 합계를 sums 배열에 넣어줌

2. while문을 돌면서 sums 배열의 가장 작은 값을 height 값으로 정함

3. for문을 돌면서 파라미터(h1, h2..)의 길이가 0보다 크고, 높이가 sums 값보다 작을 때, sums 값에서 파라미터의 첫번째 값을 빼줌

4. found를 true로 처리함 → 모든 값이 else일 때까지 반복

5. found가 false 면 while문을 끝냄

6. height를 반환함