프로그래머스 [Lv. 3] 공 이동 시뮬레이션 {언어 : JavaScript} [다시 풀어 보기, 7번 9번 테스트케이스]

문제 링크

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

프로그래머스

정답 코드

function solution(n, m, x, y, queries) {
    let minX = BigInt(x), maxX = BigInt(x);
    let minY = BigInt(y), maxY = BigInt(y);
    n = BigInt(n);
    m = BigInt(m);

    // 쿼리를 역순으로 처리합니다.
    for (let i = queries.length - 1; i >= 0; i--) {
        const [d, dist] = queries[i];
        const distance = BigInt(dist);

        if (d === 0) { // left
            if (minY > 0) minY += distance;
            maxY = maxY + distance >= m ? m - 1n : maxY + distance;
        } else if (d === 1) { // right
            if (maxY < m - 1n) maxY -= distance;
            minY = minY - distance < 0n ? 0n : minY - distance;
        } else if (d === 2) { // up
            if (minX > 0) minX += distance;
            maxX = maxX + distance >= n ? n - 1n : maxX + distance;
        } else if (d === 3) { // down
            if (maxX < n - 1n) maxX -= distance;
            minX = minX - distance < 0n ? 0n : minX - distance;
        }

        // 범위가 격자 밖으로 나가면 불가능한 경우
        if (minX > maxX || minY > maxY) return 0;
    }

    return (maxX - minX + 1n) * (maxY - minY + 1n);
}

풀이 방법

 

1. 역순 쿼리 처리: 쿼리를 정방향으로 처리하면 이동 결과를 추적하는 것이 어렵고 복잡하다. 따라서 쿼리를 역순으로 처리하여 도달 가능한 범위를 확장하는 방식으로 접근한다. 즉, 쿼리가 x와 y 좌표를 얼마나 움직였는지를 계산하기보다, 주어진 위치가 원래 어디서 왔는지를 추적한다.
2. 최소 범위(minX, minY)와 최대 범위(maxX, maxY) 추적:
   • minX, maxX: 가능한 행(row)의 최소값과 최대값을 나타낸다.
   • minY, maxY: 가능한 열(column)의 최소값과 최대값을 나타낸다.
   처음에는 시작점 (x, y)가 가능한 범위의 유일한 점이므로, minX = maxX = x, minY = maxY = y로 초기화한다.
3. 쿼리 처리: 쿼리를 역순으로 하나씩 처리하면서 가능한 범위를 확장한다. 각 쿼리는 이동 방향과 반대 방향으로 범위를 확장한다. 예를 들어, 쿼리가 "왼쪽으로 d만큼 이동"이었다면, 역순으로 처리할 때는 오른쪽으로 d만큼 이동할 수 있음을 의미한다.
   • d === 0 (왼쪽으로 이동):
     • 최소 열(minY)이 0이 아니라면, minY를 오른쪽으로 dist만큼 이동할 수 있다.
     • 최대 열(maxY)은 dist만큼 오른쪽으로 확장할 수 있다.
     • 단, 최대 열(maxY)이 격자의 크기(m - 1n)를 초과하지 않도록 제한한다.
   • d === 1 (오른쪽으로 이동):
     • 최대 열(maxY)이 m - 1n이 아니라면, maxY를 왼쪽으로 dist만큼 이동할 수 있다.
     • 최소 열(minY)은 왼쪽으로 dist만큼 확장할 수 있다.
     • 단, 최소 열(minY)이 0보다 작아지지 않도록 제한한다.
   • d === 2 (위로 이동):
     • 최소 행(minX)이 0이 아니라면, minX를 아래로 dist만큼 이동할 수 있다.
     • 최대 행(maxX)은 dist만큼 아래로 확장할 수 있다.
     • 단, 최대 행(maxX)이 격자의 크기(n - 1n)를 초과하지 않도록 제한한다.
   • d === 3 (아래로 이동):
     • 최대 행(maxX)이 n - 1n이 아니라면, maxX를 위쪽으로 dist만큼 이동할 수 있다.
     • 최소 행(minX)은 위쪽으로 dist만큼 확장할 수 있다.
     • 단, 최소 행(minX)이 0보다 작아지지 않도록 제한한다.
4. 범위 유효성 검사:
   • 매 쿼리 처리 후, minX > maxX 또는 minY > maxY가 되는 경우, 가능한 범위가 없다는 것을 의미하므로 0을 반환한다.
5. 결과 계산:
   • 모든 쿼리 처리가 끝나면 최종적으로 minX부터 maxX까지, minY부터 maxY까지의 가능한 위치의 수를 계산한다.
   • 가능한 위치의 수는 (maxX - minX + 1n) * (maxY - minY + 1n)으로 계산된다. 이 값은 도달 가능한 위치의 수를 나타낸다.

BigInt 사용 이유

• JavaScript의 일반적인 숫자(Number) 타입은 2^53 - 1보다 큰 정수를 정확하게 표현하지 못하기 때문에, 큰 수의 연산에서 오버플로우나 정밀도 문제를 방지하기 위해 BigInt를 사용했다. 이로 인해 매우 큰 값의 쿼리도 안전하게 처리할 수 있다.

 

느낀점

• 범위나 이런 부분에서 어떻게 계산해야할지 막막했고 그 과정에서 바로 틀렸다.
• 다시 풀어보려 했지만 시간이 너무 오래 걸렸고 GPT선생님의 힘을 빌렸다.
• BigInt와 범위에 대해 배울 수 있는 좋은 문제였다.