TIL 220822

알고리즘

백준

1. 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);

2. 1303 전쟁 - 전투

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

const [n, m] = input[0].split(' ').map(element => Number(element));
const graph = input.slice(1).map(element => element.split(''));
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];

function BFS(n, m, i, j, newGraph, color) {
    let result = 0;
    const queue = new Array();
    queue.push([i, j]);
    newGraph[i][j] = 'Dummy';
    
    while (queue.length > 0) {
        const [cx, cy] = queue.shift();
        result += 1;
        
        for (let i = 0; i < 4; i++) {
            const nx = cx + dx[i];
            const ny = cy + dy[i];
            
            if ((0 <= nx && nx < m) && (0 <= ny && ny < n) && (newGraph[nx][ny] === color)) {
                newGraph[nx][ny] = 'Dummy';
                queue.push([nx, ny]);
            }
        }
    }
    
    return result;
}

function solution(n, m, graph) {
    const newGraph = [...graph];
    let whiteResult = 0;
    let blueResult = 0;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (newGraph[i][j] === 'W') {
                const result = BFS(n, m, i, j, newGraph, 'W');
                whiteResult += result * result;         
            }
            
            if (newGraph[i][j] === 'B') {
                const result = BFS(n, m, i, j, newGraph, 'B');
                blueResult += result * result;
            }
        }
    }
    
    return [whiteResult, blueResult];
}

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

가로 세로를 헷갈렸다! 행의 크기가 N, 열의 크기가 M인데 반대로 생각했다. 행의 '갯수'가 N, 각 행에 있는 열의 '갯수'가 M이라고 생각했던 것이다. 하지만 문제에서 가로의 크기는 열의 갯수, 세로의 크기는 행의 갯수를 말하는 것이었다.

프로그래머스

1. 스킬트리 (Level 2)

function isSame(skill, target) {
    for (let i = 0; i < target.length; i++) {
        if (skill[i] !== target[i]) {
            return false;
        }
    }
    
    return true;
}

function solution(skill, skill_trees) {
    let result = 0;
    
    skill_trees.forEach((element) => {
        let compare = '';
        
        for (let currentSkill of element) {
            if (skill.includes(currentSkill) === true) {
                compare += currentSkill;
            }
            
            if (isSame(skill, compare) === false) {
                return;
            } 
        }
        
        result += 1;
    })
    
    return result;
}

최악의 경우 O(N3)가 되버리는 풀이인 것 같다. 다행히 문자열 길이가 26이하이고 원소가 20개 이하라서 속도 차이가 크진 않아 통과할 수 있었다.

2. 모의고사 (Level 1)

function check(person, answers) {
    let result = 0;

    for (let i = 0; i <= answers.length; i++) {
        if (answers[i] === person[i % person.length]) {
            result += 1;
        }
    }
    
    return result;
}

function solution(answers) {
    const result1 = check([1, 2, 3, 4, 5], answers);
    const result2 = check([2, 1, 2, 3, 2, 4, 2, 5], answers);
    const result3 = check([3, 3, 1, 1, 2, 2, 4, 4, 5, 5], answers);
    
    const maxValue = Math.max(result1, result2, result3);
    const result = new Array();
    
    [result1, result2, result3].forEach((element, index) => {
        if (maxValue === element) {
            result.push(index + 1);
        }
    })
    
    return result;
}

답을 어떻게 도출해야 될지 몰라서 검색을 해봤다. 그냥 max 값을 구하고 그거와 같은 것을 배열에 담으면 되는구나...라는 걸 알 수 있었다. 단순해보이지만 떠오르지 않았다.

코드도 영 가독성이 떨어지는 것 같다. 보기에 좋지도 않고! 다음에 다시 풀어봐야겠다. 그 땐 제발 떠오르길!