[Codility] Lesson 7: Stacks and Queues - StoneWall (javascript) 문제 풀이

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

StoneWall coding task - Learn to Code - Codility

- N 개의 양의 정수로 구성된 배열 H가 주어짐
- N은 돌담의 전체 길이
- H[I]는 I부터 I+1미터까지의 벽의 높이를 나타냄
- H[0]은 돌담의 왼쪽 끝, H[N-1]은 오른쪽 끝의 높이를 나타냄
- 돌담은 직육면체 석재 블록으로 만들어야 함
- 돌담을 짓는 데 필요한 최소 블록 수를 return
- 가장 효율적인 알고리즘 작성
- N은 [1..100,000] 범위의 정수
- 배열 H의 각 요소는 [1..1,000,000,000] 범위 내의 정수

 

Solution

CASE 1: 큐를 이용해 블록을 최소 단위로 자르기 - 42%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function buildBlocks(queue) {
    let block = 0;
    while(queue.length > 0){
        if(queue[0] == 0){
            queue.shift();
        }
        else if(queue[0] < 0){
            block++;
            queue.shift();
        }
        else{
            height = queue[0];
            for(let j=0; j<queue.length; j++){
                if(queue[j] != 0){
                    queue[j] -=  height;
                }
            }
            block++;
        }
    }
    return block;
}

function solution(H) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = H.length;
    let queue = [];
    let blocks = 0;
    
    queue.push(H[0]);
    for(let i=1; i<N; i++){
        if(H[i] >= queue[0]){
            queue.push(H[i]);
        }
        if(H[i] < queue[0]){
            blocks += buildBlocks(queue);
            queue.push(H[i]);
        }
    }
    blocks += buildBlocks(queue);
    
    return blocks;
}

- 큐를 이용
- H[i]가 queue[0]보다 크거나 같으면 queue에 H[i] 값을 push
- H[i]가 queue[0]보다 작으면 블록 자르기
-> 잘못된 방법!!!

 

CASE 1: Result

 

CASE 1: Analysis

The following issues have been detected: wrong answers, timeout errors.
다음과 같은 문제가 감지되었습니다. 오답, 시간 초과 오류.

 

CASE 2: 스택을 이용해 블록 수 계산 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(H) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = H.length;
    let lastH = [];
    let blocks = 0;
    
    for(let i=0; i<N; i++){
        while(lastH.length > 0 && H[i] < lastH[lastH.length-1]){
            lastH.pop();
        }
        if(lastH.length <= 0 || H[i] > lastH[lastH.length-1]){
            lastH.push(H[i]);
            blocks++;
        }
    }
    
    return blocks;
}

- lastH : 이전 블록의 높이를 저장할 스택
- blocks : 필요한 최소 블록 개수
- 스택 lastH가 비어있지 않고, H[i]가 스택 lastH의 top이 더 크면 pop
- 스택 lastH가 비어있고, H[i]가 스택 lastH의 top보다 더 크면 push하고 blocks 카운트 증가
- for문이 종료되면 blocks를 return
- while문 먼저 실행한 뒤, if문으로 스택 lastH에 push를 해줘야함 (순서가 중요!)

 

CASE 2: Result

app.codility.com/demo/results/trainingY3WV5D-E7S/

 

CASE 2: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

이 문제는 왠지 큐로 풀어야할 것 같아서 계속 큐로 시도하다가 점점 산으로 가게 되었다.
원래 의도는 H[i]가 queue[0]보다 작을 경우, queue에 있던 항목들을 기준으로 블록을 자르고 계산하고 하려고 했지만.....
이전 블록의 높이와 비교해야 하는 문제이기 때문에 스택으로 해결해야한다.

이전 블록의 높이가 현재 블록의 높이보다 높으면, 현재 블록은 이전 블록과 하나로 합쳐질 수 있으므로, 스택 lastH에서 pop을 시킨다.
스택 lastH가 비어있거나, 이전 블록의 높이보다 현재 블록의 높이가 높으면 별도의 블록 조각이 필요하므로 스택 lastH에 push하고 blocks 카운트를 증가시킨다.