[Javascript] Codility Lesson 7 - StoneWall

문제: https://app.codility.com/programmers/lessons/7-stacks_and_queues/

 

문제 요약: 

• 배열 H에 들어있는 요소는(N) 벽의 높이를 의미한다.
• H[0] = 9, H[1] = 8, H[2] = 11... 이면, 맨 왼쪽부터 높이는 9m, 8m, 11m...로 울퉁불퉁한 형태의 벽이 이루어진다.
• N의 범위는 1 ~ 100,000 이다.
• H의 범위는 1 ~ 1,000,000,000이다.
• 벽을 쌓을 때 필요한 벽돌의 최소 개수를 구하여라.

 

시도 1:

function solution(H) {
    let result = 0;
    let stack = [];

    // stack 요소의 합을 구할 때 이용할 함수
    const getH = (list) => {
        return list.reduce((prev, curr) => prev + curr, 0);
    }

    for(let i = 0; i < H.length; i++) {
    	// stack 요소의 합 (=사용한 벽돌들의 높이)
        const hSum = getH(stack);

        if (hSum === H[i]) {
            continue;
        } else if (hSum > H[i]) {
            // 사용한 벽돌들의 높이가 벽의 높이보다 높다면 맨 위에 쌓인 벽돌부터 제거
            while (getH(stack) > H[i]) {
                stack.pop();
                // 제거한 벽돌의 개수를 카운팅
                result++;
            };
            let addH = H[i] - getH(stack);
            // 사용한 벽돌들의 높이가 벽의 높이보다 낮다면 동일한 높이가 되도록 벽돌 추가
            addH > 0 && stack.push(addH);
        } else {
            stack.push(H[i] - hSum);
        }
    }
 
    // stack에 남아있는 벽돌의 개수도 카운팅
    result += stack.length;
    return result;
}

첫 번째 풀이 방법은 벽돌 높이의 합(stack에 들어있는 요소의 합)과 벽의 높이를 비교한 뒤, 비교 결과에 따라 stack에 벽돌을 제거하거나 추가하고 이에 따라 필요한 벽돌 개수를 구하였다. 예를 들면 아래와 같다.

H[0] = 8일 때, stack에 값 8을 넣고 다음 벽의 높이를 탐색한다. (stack 요소의 합: 8)

H[1] = 10일 때, stack 요소의 합(8) < 벽의 높이(10)이므로, stack.push(2) 다음 벽의 높이를 탐색한다. (stack 요소의 합: 10)

H[2] = 10일 때, stack 요소의 합(10) < 벽의 높이(10)이므로, 별다른 조치 없이 다음 벽의 높이를 탐색한다. (stack 요소의 합: 10)

H[3] = 4일 때, stack 요소의 합(10) > 벽의 높이(4)이므로, 벽의 높이 이하가 될 때까지 pop() 하며, pop()을 통해 벽돌이 stack에서 빠져나갈 때 필요한 벽돌의 개수(result)를 카운팅 한다. stack 요소의 합이 벽의 높이와 동일해졌다면 다음 벽의 높이를 탐색하고, stack 요소의 합이 벽의 높이보다 작아졌을 경우 벽의 높이와 일치하도록 값을 push 하고 다음 벽의 높이를 탐색한다.

위 풀이대로 진행했을 때 정확도는 100%였으나 퍼포먼스에서 2개가 timeout 됐다. stack 요소의 합을 구하는 getH 함수가 reduce를 사용하기 때문에 반복문 안에서 반복문을 실행하는 꼴이 되어버려 효율성이 낮아진 게 아닐까 생각한다.

 

 

시도 2:

function solution(H) {
    let result = 0;
    let currH = 0;
    let stack = [];

    for(let i = 0; i < H.length; i++) {
        if (currH === H[i]) {
            continue;
        }
        // 벽돌의 높이가 벽의 높이보다 높을 때
        if (currH > H[i]) {
            // 벽돌의 높이가 벽의 높이 이하가 될때까지
            while (currH > H[i]) {
            	// stack에서 벽돌을 제거하고
                let leaveH = stack.pop();
                // stack에 쌓인 벽돌의 높이를 업데이트하고
                currH -= leaveH;
            };
        };
        // 벽의 높이가 사용한 벽돌의 높이보다 높을 때
        if (H[i] > currH) {
            let addH = H[i] - currH;
            // stack에 벽돌을 추가하고
            stack.push(addH);
            // stack에 쌓인 벽돌의 높이를 업데이트하고
            currH += addH;
            // 사용한 벽돌의 개수를 카운팅
            result += 1;
        }
    };

    return result;
}

https://app.codility.com/

두 번째 풀이 방법으로 해결했을 때 정확도 100%, 퍼포먼스 100%이 나왔다. 기본 틀은 첫 번째 방법과 크게 변하지 않았으나, stack의 합을 구하는 함수를 따로 선언하지 않고 stack에 벽돌이 추가되거나 제거될 때마다 사용한 벽돌 높이를 업데이트하도록 했다. 이 외에 벽돌이 추가될 때 result를 카운팅 함으로써 for문 밖에서 stack의 잔여 요소 개수를 합하는 코드를 제거였고, if 문을 반복 사용하여 중복된 코드는 제거했다.