링크
공 이동 시뮬레이션
난이도
문제요약
- 2차원 행렬에서 이동 쿼리를 적용해서 이동시킨다음, 특정 좌표(x,y)지점에 도착하는 지점의 갯수를 구하기
- 만약 벽끝이면 이동을 안하고 그자리에 멈춤
- 쿼리는 [방향(좌0우1상2하3), 이동거리(1이상)]로 된다.
접근
- 2차원행렬을 만들어서 쿼리를 직접 실행하여 확인
- 좌우 / 상하의 1차원 행렬을 각자 만들어서 좌우 움직임과, 상하 움직임을 따로 쿼리를 적용
- 좌우에서 x값, 상하에서 y값을 곱한다.
- 시간초과 - 이때부터 열받음
- 좌우, 상하의 컨셉은 유지하면서 실제 이동을 하나씩 시키지 않고 이동거리를 바로 적용해서 한번에 계산하기
접근 상세
- 이 문제를 어떤식으로 계산하는지 확인해보자
- 제일 간단한 방식
- 모든 배열에 1씩 부여하고 직접 쿼리를 적용하는것이다.
- 위처럼 표의 칸 마다 1을 가지고 있고 이동을 직접 적용해서 왼쪽으로 간다면
- 값이 날아가지 않고 겹쳐서 1+1되어 2가 된다.
- 이는
쿼리를 수행후에는 해당 지점에 도착하는게 몇개의 지점이 있는지를 보여준다.
- 문제 집중할 부분
- 먼저 위의 계산이 이해가 된다면 위의 계산을 최대한 축약하는걸 집중하였다.
- 모든 배열을 다 직접 이동시켜야 할 필요 없음
- 좌우와 상하마 따로 뺀 1차원 행렬 두개로도 충분히 계산이 된다.
- 위처럼 가로배열 세로배열만 따로 뺀다면 좌우로 움질일때는 가로 배열에서 계산이 이뤄지고, 상하로 움직일때는 세로 배열에서 계산이 이루어진다.
- 이렇게 생각할 수 있는 이유는 상하와 좌우 두개의 위치는 서로 간섭이 없기 때문이다.
- 그림은 이해를 돕기위해 세로배열을 세웠지만 가로로 눞혀서 계산하면 좀더 이해하기 쉽게 계산을 할 수 있다.
- 그럼 최종 x,y에서의 결과는 어떻게 계산되나
- 실제 배열은 x,y의 값을 불러 오면 되지만 여기서는
가로배열의 x위치의 값 * 세로배열의 y위치의값으로 나타낼 수 있다.
- 곱하는 이유를 좀더 말로 설명하자면 가로 배열위에 세로 배열을 각자 가지고 있다고 보면 된다.
- 위처럼 가로와 배열 두개의 1차원 배열만 해도 시간초과가 일어난다.
- 줄이는 방법은 직접 이동을 한칸씩 하는게 아니라 한번에 계산해야한다.
- 겹쳐지는게 몇개인지 이동후 결과를 바로 알 수 있는 방식이 필요하다.
간단 알고리즘
- n(가로), m(세로), x, y(목표 좌표), queries(쿼리들)가 주어지고 시작
- 추가 변수
[0 6 1 1 ... 1 1 18 0 0 0]이 있을때 규칙이 보일것이다.- 무조건 겹쳐지는 부분은 양쪽이 될수밖에 없고, 중첩 사이 가운데는 1들 만 존재한다.
- 중첩된 부분 밖은 전부 0이다.
- 우리가 필요한 변수
1과 중첩 영역위치를 가지는 checkWL,checkWR(checkHL,checkHR)중첩된 왼쪽끝, 오른쪽끝의 중첩값 checkWLV,checkWRV(checkHLV,checkHRV)
- 말이 중첩이지 결국 0이 아닌 부분의 제일 끝쪽의 좌표와 값이다. 중첩은 결국 끝만 되니 중첩이라 표기하겠다.
- 예외 하나
[0 0 0 0 10 0 0 0 ]처럼 만약 중첩이 하나로 만들어진 경우는 값은 왼쪽값 checkWLV(checkHLV)하나로 관리하도록 한다.
- 반복문
- queries를 하나씩
변수 q에서 확인
- q는 [방향, 이동거리]를 가지고 있다.
- 왼쪽 이동(위로 이동)
- 초기화
checkWL=0, checkWR=n-1, checkWLV=1,checkWRV=1
- 만약 checkWL과 checkWR이 같은경우
- 하나의 중첩된 위치만 가진 경우이다.
- checkWL-=q[1], checkWR-=q[1]로 이동 진행
- checkWL<0이면 왼쪽 끝에 도달했다는 의미로 checkWL=0, checkWR=0으로 부여
- 다른 경우
- 이동 진행
- checkWL-=q[1], checkWR-=q[1]
- checkWR<=0인경우
- 왼쪽으로 이동하는데 오른쪽의 좌표가 0이 된것은 결국
왼쪽에서 중첩된것을 의미
- checkWR=0,checkWL=0으로 0의 좌표로 지정
- checkWLV=n으로 최대값을 부여해줌, checkWRV=0으로 왼쪽값으로 관리하기때문에 0으로 해줌
- checkWL<0인경우
- 두 좌표가 중첩은 없지만, 왼쪽 좌표가 밖으로 나갔다는 것을 의미
- checkWLV = checkWLV - checkWL
- checkWL을 빼주는 이유는 이미 -좌표가 되고 삐져나온만큼 더해야 하기때문에 빼기를 진행
- 좀더 설명
[13 1 1[1 1 1 ...]]이런식으로 괄호로 표현한것으로 보자면 13,1,1이 밖으로 나가 중첩 계산을 해줘야한다,- 밖으로 나간 원소의 갯수는 3개가 되고 이를 왼쪽 중첩 값과 더해주면 13+3으로 16으로 해주면 된다.
[16 1 1 ...]로 계산이된다.- 좀더 보기쉽게 수정하면 이것과 같은 계산으로 생각하면 된다.
[1 1 1[13 1 1 1 ...]]애초에 오른쪽 끝과 중첩이 안된 전재이기 때문에 문제없이 작동한다.
- checkWL=0으로 0으로 좌표 지정
- 그외
- 중첩도 안되고 그저 좌표 이동만 된 상황으로 추가 계산은 필요 없음
- 오른쪽 이동(아래로 이동)
- 만약 checkWL과 checkWR이 같은경우
- 하나의 중첩된 위치만 가진 경우이다.
- checkWL+=q[1], checkWR+=q[1]로 이동 진행
- checkWL>=m-1이면 오른쪽 끝에 도달했다는 의미로 checkWL=m-1, checkWR=m-1으로 부여
- 다른 경우
- 이동 진행
- checkWL+=q[1], checkWR+=q[1]
- checkWL>=m-1인경우
- 오른쪽으로 이동하는데 왼쪽의 좌표가 m-1이 된것은 결국
오른쪽에서 중첩된것을 의미
- checkWR=m-1,checkWL=m-1으로 0의 좌표로 지정
- checkWLV=n으로 최대값을 부여해줌, checkWRV=0으로 왼쪽값으로 관리하기때문에 0으로 해줌
- checkWR>m-1인경우
- 두 좌표가 중첩은 없지만, 오른쪽 좌표가 밖으로 나갔다는 것을 의미
- checkWRV = checkWRV + (checkWR - (m-1))
- 오른쪽으로 빠져나온것은 우측 끝의 좌표(m-1)를 빼주면 된다.
- 괄호가 없이 checkWR-m-1로 쓰면 checkWR-m+1로 계산된다. 괄호를 잘 써주자
- checkWR=m-1으로 우측 끝 m-1로 좌표 지정
- 그외
- 중첩도 안되고 그저 좌표 이동만 된 상황으로 추가 계산은 필요 없음
- 위쪽, 아래쪽 이동
- checkWL,checkWR -> (checkHL,checkHR)
- checkWLV,checkWRV -> (checkHLV,checkHRV)
- m->n으로 바꾸면 됨
시간초과 설명
- 행렬 문제
- 만약 행렬을 만들어서 푸는데 시간초과나면 확인해야 하는 사항
- 행렬은 n,m으로 결정된다.
- n과 m은 10^9로 1000000000이다.
- 이를 행렬로 직접 만들려고 한다면 시간초과가 발생해서 내가 원하는 방식으로 행렬 계산이 안된다.
- 쿼리 문제
- 위에서 행렬을 안쓴다고 하더라도 시간초과나면 확인해야 하는 사항
- 쿼리의 이동 범위는 10^9로 1000000000이다.
- 반복문으로 직접 돌아간다고 하면 10^9(이동거리) * 200,000(쿼리갯수)가 된다.
- 엄청 많다
- 결국 직접 다 수행하는게 아닌 해당 쿼리에서 바로 결과를 계산해야 시간초과를 이겨낼 수 있다.
후기
- 엄청 오래걸림
- 프로그래머스 해설을 보고와도 시간초과 해결을 못함
- 행렬문제처럼 보였는데 행렬없이 풀었음
- 10^9(1000,000,000)크기의 배열을 만드는것으로도 시간초과 나옴
- 한 일주일 동안 두통때문에 제대로 못풀다 이제야 품