https://school.programmers.co.kr/learn/courses/30/lessons/87391
프로그램 제작자
코드 중심 개발자를 고용하십시오. 배치 기반 위치 매칭. 프로그래머의 개발자별 프로필에 가입하고 기술 호환성이 좋은 회사와 연결하십시오.
Programmer.co.kr
첫 번째 접근
문제에 제시된 시뮬레이션에 따르면
각 좌표를 돌아다니다
쿼리가 실행될 때
x,y 목표 지점으로 가고 있는지 확인
시간 초과 이유
n*m*쿼리
최악의 경우를 선택하라
10^9 * 10^9 *200000
그러면 어떻게 고칠 수 있습니까?
구글 검색을 통해 찾은 방법입니다.
1. 쿼리만 실행하도록 수정해도
200,000으로 대폭 줄었습니다.
2. 쿼리를 반대로 하여
모든 것이 준비되면 x점과 y점에 도달했는지 여부를 판단합니다.
3. 포인트가 x, y 포인트에 모인다고 생각하고,
점선 영역을 직사각형으로 생각하십시오.
이미지 설명
x와 y가 0,0이라고 가정
문제를 설명하겠습니다.
x,y 지점에는 하나의 지점만 있습니다.
쿼리 ty==2 및 dx==2인 경우
이것은 줄이 무너졌을 때입니다.
이 작업을 수행할 때 어떤 좌표가 0,0인지 추적하면
위의 그림처럼 그릴 수 있습니다.
다시 생각 해봐
xMax 증가
이것이 x와 y의 최대값과 최소값을 찾는 방법입니다.
“점이 있는 직사각형의 면적”이라고 생각하시면 됩니다.
케이스가 범위를 벗어난 경우
답은 0이어야 합니다.
x,y가 0,0인 상황에서
ty==3은 부동이므로 볼의 최대값이 범위를 벗어났습니다.
반대로 공은 손이 닿지 않는 곳으로 갔다
당신이 이전에 무엇을 했는지에 관계없이 그것은 결국 도달할 수 있는 공이 없다는 것을 의미합니다.
그냥 0을 반환합니다.
여기서 주의할 점은
Min과 Max가 함께 움직일 수 있다는 사실.
x,y가 0,0이고 ty==2일 때 xMin은 고정되지만
1.0의 경우 xMin도 함께 움직입니다.
코드를 처음 봤을 때 그게 무슨 뜻인지 이해하지 못했습니다.
직접 그림을 그려보니 이해가 가네요.
선이 하나씩 줄어들어 1.0이 되는 좌표를 플로팅하면,
거기에 딱 하나의 경우가 있습니다.
따라서 점이 있는 사각형을 찾으면
xMin 값도 이동해야 합니다.
이런 식으로 다른 경우에는 그림이 그려지는 반면,
“만약에?”를 염두에 두고 코드를 작성하는 것이 좋습니다.
암호
def solution(n, m, x, y, queries):
answer = 0
# 공이 한번에 움직인다고 생각한다
# 공의 범위를 사각형으로 두고 생각해보자
# 역으로 생각한다
queries.reverse()
xMin, xMax, yMin, yMax = x, x, y, y
# print(queries)
for ty, dx in queries:
# 원래 열감소니깐 여기서는 열증가로 계산
if ty == 0:
yMax += dx
if yMax >= m:
yMax = m - 1
if yMin != 0:
yMin += dx
# 원래는 열증가니깐 여기서는 열감소로 계산
elif ty == 1:
yMin -= dx
if yMin < 0:
yMin = 0
if yMax != m - 1:
yMax -= dx
# 원래는 행감소니깐 여기서는 행증가로 계산
elif ty == 2:
xMax += dx
if xMax >= n:
xMax = n - 1
if xMin != 0:
xMin += dx
# 원래는 행 증가니깐 여기서는 행감소로 계산
elif ty == 3:
xMin -= dx
if xMin - dx < 0:
xMin = 0
if xMax != n - 1:
xMax -= dx
# 범위를 벗어나는 케이스가 생긴다면 공이 없다
# print(xMin,xMax,yMin,yMax)
if xMin > n or xMax < 0 or yMin > m or yMax < 0:
return 0
else:
answer = (xMax - xMin + 1) * (yMax - yMin + 1)
return answer