TIL 220815

알고리즘

백준

1. 1920 수 찾기

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]);
const arrayN = input[1].split(' ').map(element => Number(element));
const m = Number(input[2]);
const arrayM = input[3].split(' ').map(element => Number(element));

function isValid(newArrayN, target) {
    let left = 0;
    let right = newArrayN.length - 1;
    
    while (left <= right) {
        const mid = parseInt((left + right) / 2);
        if (newArrayN[mid] === target) {
            return 1;
        } else if (newArrayN[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return 0;
}

function solution(arrayN, arrayM) {
    const newArrayN = [...arrayN].sort((a, b) => a - b);
    let result = new Array();
    
    arrayM.forEach((element) => {
        result.push(isValid(newArrayN, element));
    })
    
    return result;
}

const result = solution(arrayN, arrayM);

// 왜 forEach가 아니라 join으로 해야 시간 초과가 나지 않을까?
console.log(result.join('\n'));
// result.forEach((element) => {
//     console.log(element);
// })

이거 왜 forEach를 활용해서 console.log를 찍으면 시간 초과가 발생하는 거지? 찾아봐도 join의 시간 복잡도에 대한 자료는 잘 안보여서 질문글로는 올려놨는데... 백준은 정답 출력도 시간 복잡도에 포함이 되니 더 까다로운 것 같다...

2. 2178 미로 탐색

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('').map(element => Number(element)))

function solution(n, m, graph) {
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    const newGraph = [...graph];
    
    const queue = new Array();
    queue.push([0, 0, 1])
    newGraph[0][0] = 1;
    
    while (queue.length !== 0) {
        let count = queue[0][2];
        const [cx, cy] = queue.shift();

        for (let i = 0; i < 4; i++) {
            const nx = cx + dx[i];
            const ny = cy + dy[i];
            
            if ((0 <= nx && nx <= n - 1) && (0 <= ny && ny <= m - 1) && (newGraph[nx][ny] === 1)) {
                newGraph[nx][ny] = 0;
                
                if (nx === n - 1 && ny === m - 1) {
                    return count + 1;
                }
                
                queue.push([nx, ny, count + 1]);
            }
        }
    }
}

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

원래는 count 변수 증가를 newGraph[nx][ny] = 0; 아래에 뒀는데, 이러면 count는 좌우상하 상관 없이 그냥 1씩 증가한다. 예를 들면 count가 2이고 (2, 2) 좌표에서 상하좌우 다 갈 수 있다는 가정하에, 즉 상하좌우 모두 1이라는 가정하에 queue에는 (1, 2, 2 + 1), (2, 3, 2 + 1), (3, 2, 2 + 1), (2, 2, 2 + 1)과 같이 각각 count가 3이 들어가야 한다. 하지만 나는 그냥 각각 3, 4, 5, 6씩 넣어버리는 실수를 범했던 것이다. 이거 찾는다고 애 좀 먹었다... 위 처럼하면 while문에서 한 블록 안의 count에는 영향을 끼치지 않는다. 따라서 const로 선언해도 된다. ㅎㅎㅎ! 실수했던 방법대로 하면 count가 재할당되니 let으로 선언해놓아야 했다.

하루를 마치고

자바스크립트로 알고리즘을 풀 때 queue를 위해 배열을 사용하는데, 앞의 것을 빼내기 위해서는 shift라는 메소드를 사용해야한다. 이는 파이썬 deque의 popleft와는 차이가 있다. shift의 경우는 앞의 것을 빼면 뒤의 것들이 앞 쪽으로, 말 그대로 shift 되는지 시간 복잡도가 O(N)이다... popleft는 O(1)인데... 나중에 이러한 차이로 시간 초과가 발생할 수 있지 않을까 싶다. 그 땐 queue를 구현해야 하나?