TIL 220821

알고리즘

백준

1. 2805 나무 자르기

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = Number(input[0].split(' ')[0]);
const m = Number(input[0].split(' ')[1]);
const trees = input[1].split(' ').map((element) => Number(element));

function check(currentHeight, newTrees) {
    let result = 0;
    
    newTrees.forEach((element) => {
        if (element >= currentHeight) {
            result += element - currentHeight;
        }
    })
    
    return result;
}

function solution(n, m, trees) {
    const newTrees = [...trees];
    newTrees.sort((a, b) => a - b);
    
    let start = 0;
    let end = newTrees[newTrees.length - 1];
    let result = Number.MIN_SAFE_INTEGER;
    
    while (start <= end) {
        const mid = parseInt((start + end) / 2);
        
        if (check(mid, newTrees) >= m) {
            start = mid + 1;
    
            if (mid > result) {
                result = mid;
            }
        } else {
            end = mid - 1;
        }
    }
    
    return result;
}

const result = solution(n, m, trees);
console.log(result);

후... start를 처음엔 newTrees의 처음, 나중엔 1으로 해두었어서 반례가 존재했기에 틀렸었다. 0이어야 하는 이유를 몰랐던 것이다.

3 10
1 4 5

위와 같은 예시가 존재한다면, 톱날의 높이는 0이어야 1, 4, 5를 얻어서 상근이는 10미터의 나무를 가지고 갈 수 있게 된다. 따라서 시작(start)이 0이어야 하는 예시가 존재했던 것이다.

2. 10773 제로

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const k = Number(input[0]);
const numberArray = input.slice(1).map(element => Number(element));

function solution(k, numberArray) {
    const stack = new Array();
    
    numberArray.forEach((element) => {
        if (element === 0 && stack.length !== 0) {
            stack.pop();
            
            return;
        }
        
        stack.push(element);
    })
    
    if (stack.length === 0) {
        return 0;
    }
    
    const result = stack.reduce((previous, current) => {
        return previous += current;
    })
    
    return result;
}

const result = solution(k, numberArray);
console.log(result);

프로그래머스

1. 캐시 (Level 2)

function solution(cacheSize, cities) {
    const cache = new Array();
    const newCities = [...cities].map(element => element.toLowerCase());
    let result = 0;
    
    newCities.forEach((element) => {
        let index;
        if ((index = cache.indexOf(element)) !== -1) {
            cache.splice(index, 1);
            cache.push(element);
            result += 1;
            
            return;
        }
        
        if (cache.length >= cacheSize) {
            cache.shift();
        }
        
        if (cacheSize !== 0) {
            cache.push(element);
        }
        
        result += 5;
    })
    
    return result;
}

cache hit가 발생한 element는 cache 배열의 맨 마지막으로 가야 한다. 최신으로 업데이트 해줘야 한다. 그래야 나중에 cache가 꽉 차서 1개를 빼야할 때, 잘못된 것이 안 빠질 수 있다. cache 배열에서 맨 앞 원소(element)는 가장 먼저 차있었던 것이므로 참조된지 가장 오래되었다고 생각하고 풀었기 때문이다. 처음엔 이걸 놓쳤었다! 업데이트 해주니 대부분 통과! 2개 빼고...

두 번째로 놓친 건 cacheSize가 0인 테스트 케이스가 주어졌을 때이다. 0이면 cache에 element를 push 해주면 안되는데 push 해주고 있었다. 이를 처리하니 다 통과할 수 있었다.

2. 2016년 (Level 2)

function solution(a, b) {
    const months = [0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    const days = ['THU', 'FRI', 'SAT', 'SUN', 'MON', 'TUE', 'WED'];
    let totalDays = 0;
    
    for (let i = 0; i < a; i++) {
        totalDays += months[i];
    }
    
    totalDays += b;
    
    return days[totalDays % 7];
}

3. 소수 만들기 (Level 1)

let result = 0;

function isPrime(currentArray) {
    const sumNumber = currentArray.reduce((previous, current) => {
        return previous + current;
    })
    
    for (let i = 2; i <= Math.sqrt(sumNumber); i++) {
        if (sumNumber % i === 0) {
            return false;
        }
    }
    
    return true;
}

function DFS(nums, x, currentArray) {
    if (currentArray.length === 3) {
        if (isPrime(currentArray) === true) {
            result += 1;
        }
        return;
    }
    
    for (let i = x; i < nums.length; i++) {
        const newCurrentArray = [...currentArray];
        
        newCurrentArray.push(nums[i]);
        DFS(nums, i + 1, newCurrentArray);
    }
}

function solution(nums) {
    const newNums = [...nums];
    DFS(newNums, 0, new Array());
    
    return result;
}

자바스크립트 + DFS를 이용한 조합 구하기로 풀려고 하니 난이도가 상승되는 느낌이다... 다른 사람들의 풀이를 보니 for문으로 푼 것 같다.

그리고 파이썬에서는 따로 처리해주지 않았던 것 같은데(잘 기억이 안난다...), 계속 블록마다 복사를 해줘야 하니 더 까다로운 느낌이다. 이 부분을 놓치면 당연히 조합을 구할 수 없다.

리트코드

1. Two Sum

var twoSum = function(nums, target) {
    const initialNums = [...nums];
    const newNums = [...nums].sort((a, b) => a - b);
    let left = 0;
    let right = nums.length - 1;
    
    // 문제에서 정확히 하나의 솔루션이 있다고, 즉 하나의 답이 꼭 존재한다는 것이니까
    // while (true)로 해도 상관 없을 것 같다. (실제로 true로 바꿨는데 답이나 성능에 전혀 문제 없었다)
    // 어차피 left <= right가 깨지기 전에 답이 나올거니까
    while (left <= right) {
        if (newNums[left] + newNums[right] === target) {
            const newLeft = initialNums.indexOf(newNums[left]);
            initialNums.splice(newLeft, 1, 'dummy');
            const newRight = initialNums.indexOf(newNums[right]);
            
            return [newLeft, newRight];
        }
        
        if (newNums[left] + newNums[right] > target) {
            right -= 1;
        }
        
        if (newNums[left] + newNums[right] < target) {
            left += 1;
        }
    }
};

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
};

2개의 방법으로 풀었는데, 성능상으로는 크게 유의미한 차이가 보이진 않는다. 둘다 100ms대로 나온다. 처음 방법이 더 빠를 것으로 예상했는데 결국 while 문 안에서 indexOf를 쓰니 O(n2)가 되는 것 같다.

원티드 프리온보딩 프론트엔드 과제

• 원티드 프리온보딩 프론트엔드 과제