[프로그래머스] 87391 공 이동 시뮬레이션 (javascript)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87391

풀이

우선, 완전 탐색의 경우 $O(n \times m \times q)$ 의 시간복잡도를 가지며 최대 $10^9 \times 10^9 \times 10^5$ 의 연산이 필요하다. 이는 2억회가 아득히 넘는 연산량이므로, 완전 탐색으로는 해결할 수 없는 문제임을 알 수 있다.

결과가 정해진 문제이므로 결과로부터 역으로 진행하는 방식으로 접근해야하는 것을 어렵지 않게 알 수 있었다.

처음에는 질의를 역순으로 처리하면서 후보 시작 좌표들의 집합을 직접 업데이트하는 방식으로 구현했다. 그런데 구현하다 보니, 후보 시작 좌표들은 항상 하나의 직사각형 범위로 표현할 수 있다는 것을 깨달았다.

돌아보며 생각해보면, $n = m = 10^9$ 이고, $x = 0$ 같은 극단적인 케이스에서는 후보 시작 좌표의 집합의 크기가 $n \times m$ 이 될 수 있기 때문에, 집합을 직접 저장하는 방식은 시간 초과는 물론이고 메모리 초과까지도 충분히 날 수 있었을 것 같다.

수학적, 컴퓨터적 사고와 직관이 도움이 되는 경우가 참 많은 것 같다. 증명을 빡빡하게 적진 않았지만, 역순으로 범위를 갱신하면서 경계를 잘 보정해주면 정답이 유지된다는 직관과 감각이 요구되는 문제였던 것 같다. 그래도 다른 문제보다는 비교적 테스트 케이스를 통해 머리속으로 혹은 직접 그려가며 시뮬레이션 할 수 있어서 그렇게 어렵진 않았던 것 같다.

추가로, javascript로 문제를 풀어서 자료형에 대해 깊이 생각을 안해서 틀렸었는데, BigInt로 자료형을 바꿔주니 정답이 나왔다. 동적 타입 언어에서 자료형을 고려해야한다는 것은 참 어려운 일인 것 같다.

정답 코드

javascript

const DIRECTION = Object.freeze({
    LEFT: 0,
    RIGHT: 1,
    UP: 2,
    DOWN: 3,
});

const solution = (n, m, x, y, queries) => {
    let minX = x, minY = y;
    let maxX = x, maxY = y;
    
    for (let i = 0; i < queries.length; i++) {
        const [ direction, dist ] = queries[queries.length - 1 - i];
        
        if (direction === DIRECTION.LEFT) {
            minY = minY === 0 ? 0 : minY + dist;
            maxY = Math.min(maxY + dist, m - 1);
        } else if (direction === DIRECTION.RIGHT) {
            minY = Math.max(minY - dist, 0);
            maxY = maxY === m - 1 ? m - 1 : maxY - dist;
        } else if (direction === DIRECTION.UP) {
            minX = minX === 0 ? 0 : minX + dist;
            maxX = Math.min(maxX + dist, n - 1);
        } else if (direction === DIRECTION.DOWN) {
            minX = Math.max(minX - dist, 0);
            maxX = maxX === n - 1 ? n - 1 : maxX - dist;
        }
        
        const isOutOfBounds = n <= minX || maxX < 0 || m <= minY || maxY < 0;
        const isEmptyRange = maxY < minY || maxX < minX;

        if (isOutOfBounds || isEmptyRange) {
            return 0n;
        }
    }
    
    const rows = BigInt(maxX - minX + 1);
    const cols = BigInt(maxY - minY + 1);
    
    return rows * cols;
}

[프로그래머스] 87391 공 이동 시뮬레이션 (javascript)

문제

풀이

정답 코드

Share this post