4월 1-2주차 알고리즘 (1)

[EJSohn]

물 가두기

각각의 값이 가로가 1인 블록의 높이를 의미하는 n개의 양의 정수 배열을 입력으로 받는다. 이 때 비가 온 후 얼마나 많은 양의 물이 블록에 가둬지는지 계산하는 알고리즘을 짜시오

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Hint

• stack이나 multi-pointer를 이용해 구현할 수 있다.

[kyunooh]

1차 답안

function answer(input) {
    var stack = [];
    var maxHeight = 0;
    for(var i = 0; i < input.length; i++) {
        if(input[i] > maxHeight) maxHeight = input[i];
    }
    console.log(maxHeight);
    for(var i = 0; i < maxHeight; i++) {
        stack.push([]);
        for(var j = 0; j < input.length; j++) {
            if(input[j] > i) stack[i].push(1);
            else stack[i].push(0);
        }
    }
    var count = 0;
    var tempCount = 0;
    for(var i = 0; i < maxHeight; i++) {
        var leftEnd = true;
        tempCount = 0;        
        for(var j = 0; j < input.length; j++) {
            if(stack[i][j] === 1) {
                if(leftEnd) {
                    leftEnd = false;
                } 
                tempCount = 0;        
            } else {
                if(!leftEnd) {
                    count++;
                    tempCount++;
                }
            }
            if(j == input.length - 1) {
                count -= tempCount;
            }
        }
    }
    console.log(stack);
    return count;
}

[kyunooh]

2차답안

function answer(input) {
    var stack = [];
    var maxHeight = -1;
    var currentHeight = 0;
    var count = 0;
    for(var i = 0; i < input.length; i++)
        if(input[i] > maxHeight) maxHeight = input[i];

    while(maxHeight !== currentHeight) {
        var tempCount = 0;
        var leftEnd = true;        
        for(var j = 0; j < input.legnth; j++) {
            if(input[j] > currentHeight) {
                if(leftEnd) {
                    leftEnd = false;
                } 
                tempCount = 0;        
            } else {
                if(!leftEnd) {
                    count++;
                    tempCount++;
                }
            }
            console.log(count);
            if(j === input.length - 1) {
                count -= tempCount;
            }
        }
        console.log(maxHeight, "  ", currentHeight)
        currentHeight++;
    }
    return count;
}

var input = [0,1,0,2,1,0,1,3,2,1,2,1];

answer(input);

[kyunooh]

시청자 초초초 모범답안 공간 및 시간 복잡도 O(n) https://ideone.com/XsAY3y

[su-apollo]

https://ideone.com/mAWQ73

[EJSohn]

아니 시청자라니 방송에서 푸셨군여ㅋㅋㅋㅋㅋ

[joshuakimDwan]

SAMPLE_INPUT = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
SAMPLE_OUTPUT = 6
SAMPLE_INPUT2 = [0, 0, 2, 0, 5, 0, 1, 2, 0, 4, 1, 0]
SAMPLE_OUTPUT2 = 15

# TODO: 더 컴팩트하게 만들 수 있을 것 같다.
def count_0_between_1_and_1(list):
    total_count = 0
    count = 0
    start = False
    for el in list:
        if start:
            if el:
                total_count += count
                count = 0
                continue
            else:
                count += 1
        else:
            if el:
                start = True
                continue
            else:
                continue
    return total_count

def confine_water(h_list):
    if not h_list:
        return 0
    max_height = max(h_list)
    list_of_stack = []
    for i in range(max_height):
        list_of_stack.append([])
        for idx, height in enumerate(h_list):
            if height > 0:
                list_of_stack[i].append(1)
                h_list[idx] = max(h_list[idx] - 1, 0)
            else:
                list_of_stack[i].append(0)

    total_count = 0
    for stack in list_of_stack:
        total_count += count_0_between_1_and_1(stack)
    return total_count

if __name__ == '__main__':
    assert count_0_between_1_and_1([1]) == 0
    assert count_0_between_1_and_1([0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1]) == 2
    assert count_0_between_1_and_1([0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1]) == 5

    assert confine_water(SAMPLE_INPUT) == SAMPLE_OUTPUT
    assert confine_water(SAMPLE_INPUT2) == SAMPLE_OUTPUT2

[EJSohn]

컴파일은 이쪽에서: https://leetcode.com/problems/trapping-rain-water/