[CodeKata] 프로그래머스(Lv3) : 공 이동 시뮬레이션

🥋 Oooth More!! (Level 3) 

쿼리 실행 애니메이션은 문제 링크를 참고해주세요!

 

 

 

🧮 풀이

단순히, 모든 칸을 방문하며 쿼리를 순회하는 코드를 만들어보았고, 예상했듯이 시간초과가 미친듯이 터졌다!! 

function moveQuery(now, query, n, m) {
  let [x,y] = now
  const [cmd,v] = query
  if (cmd === 0) y = y-v < 0 ? 0 : y-v
  else if (cmd === 1) y = y+v > m-1 ? m-1 : y+v
  else if (cmd === 2) x = x-v < 0 ? 0 : x-v
  else x = x+v > n-1 ? n-1 : x+v
  return [x,y]
}

function solution(n, m, x, y, queries) {
  var answer = 0
  for (let i = 0 ; i < n ; i++) {
    for (let j = 0 ; j < m ; j++) {
      let now = [i,j]
      for (let q of queries) {
        now = moveQuery(now, q, n, m)
      }
      if (now[0] === x && now[1] === y) answer++;
    }
  }
  return answer;
}

 

 

 

🖇 리뷰

모범답안을 보니 쿼리를 역순으로 실행하는게 포인트다.

타겟좌표로부터 쿼리를 역으로 돌리며, 좌표가 포함될 수 있는 영역을 산출하는 방법이다.

function solution(n,m,x,y,queries) {
  let xt = xb = x, yl = yr = y
  queries = queries.reverse()
  
  for (let q of queries) {
    const [cmd, v] = q
    if (cmd === 0) {	// 우로 열 확장
      if (yl > 0) yl += v
      yr = Math.min(yr+v,m-1)
    }
    else if (cmd === 1) {	// 좌로 열 확장
      if (yr < m-1) yr -= v
      yl = Math.max(yl-v,0)
    }
    else if (cmd === 2) {	// 아래로 행 확장
      if (xt > 0) xt += v
      xb = Math.min(xb+v,n-1)
    }
    else {	// 위로 행 확장
      if (xb < n-1) xb -= v
      xt = Math.max(xt-v,0)
    }

    if (xt > n-1 || xb < 0 || yl > m-1 || yr < 0) return 0;
  }
  
  return (xb-xt+1) * (yr-yl+1)
}

출처의 모범답안 코드들이 Java였던 관계로, Javascript로 새로 작성했다.

 

• xl, xr은 가능한 x좌표들의 영역이 될 좌측기준과 우측기준, yt, yb는 가능한 y좌표들의 영역이 될 상한기준과 하한기준이다.
• queries를 역으로 순회해서 영역을 산출해야하므로, reverse() 메서드로 뒤집어준다.
• 다음으로, 이 queries를 순회한다. 이 때, 각 쿼리(q)들을 역으로 조회하기 때문에 각각의 이동방향 역시 반대로 반영해야한다. q의 첫번째 인자를 cmd(이동방향), 두번째 인자를 v(이동량)로 선언한다.
  • cmd가 0이면 좌측으로 이동하는 커맨드로, 반대인 우측으로 열기준을 이동한다. yl, yr에 v를 더해준다. yr은 m-1보다 커지면 안되므로 Math.min() 으로 값을 제한한다.
  • cmd가 1이면 우측으로 이동하는 커맨드로, 반대인 좌측으로 열기준을 이동한다. yl, yr에 v를 빼준다. yl은 0보다 작아지면 안되므로 Math.max() 로 값을 제한한다.
  • cmd가 2면 위로 이동하는 커맨드로, 반대인 아래로 행기준을 이동한다. xt, xb에 v를 더해준다. xb는 n-1보다 커지면 안되므로 Math.min() 으로 값을 제한한다.
  • cmd가 3이면 아래로 이동하는 커맨드로, 반대인 위로 행기준을 이동한다. xt, xb에 v를 빼준다. xt는 0보다 작아지면 안되므로 Math.max() 로 값을 제한한다.
  • 만약, 최소기준(xt, yl)이 끝값보다 커지거나, 최대기준(xb, yr)이 0보다 작아지면 모든 좌표에서 목표좌표에 도달하는 경우가 없는 것이다. 이 때는, 0을 반환한다.
• 위 queries 순회가 완료되면, (xt ~ xb) * (yl ~ yr) 영역의 좌표들은 목표좌표(x,y)로 이동이 가능한 좌표들인 것이다. 이 개수를 최종적으로 반환해주면 된다.

 

 

풀이 자체가 어렵진 않았으나, 조건에 부합하는 좌표의 영역들을 찾으려한다는 점, 그리고 이를 위해 쿼리를 역으로 추적한다는 방법을 발상하는 것이 기발한 풀이었다.

 

 

* 출처

- intrepidgeeks 님의 블로그 : https://intrepidgeeks.com/tutorial/programmer-ball-movement-simulation-java  

- eno1993 님의 블로그 : https://eno1993.tistory.com/165