Level 3 공 이동 시뮬레이션 Python 3

https://programmers.co.kr/learn/courses/30/lessons/87391?language=python3 

코딩테스트 연습 - 공 이동 시뮬레이션

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_공이동시뮬레이션.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(n, m, x, y, queries):
    sr, sc, er, ec = x, y, x, y
    for d, dx in reversed(queries):
        if d == 0:
            if sc == 0:
                ec = min(m-1, ec+dx)
            else:
                if sc+dx >= m: return 0
                sc = min(m-1, sc+dx)
                ec = min(m-1, ec+dx)
                
        elif d == 1:
            if ec == m-1:
                sc = max(0, sc-dx)
            else:
                if ec-dx < 0: return 0
                sc = max(0, sc-dx)
                ec = max(0, ec-dx)
                
        elif d == 2:
            if sr == 0:
                er = min(n-1, er+dx)
            else:
                if sr+dx >= n: return 0
                sr = min(n-1, sr+dx)
                er = min(n-1, er+dx)
                
        else:
            if er == n-1:
                sr = max(0, sr-dx)
            else:
                if er+dx < 0: return 0
                sr = max(0, sr-dx)
                er = max(0, er-dx)
                
    return (er-sr+1)*(ec-sc+1)

---

풀이 과정

이 문제의 핵심은 쿼리를 역순으로 돌아서 정답 칸에서 시작해서 쿼리를 돌면서 가능한 시작점의 범위를 구해나가는 것이다.

시작점의 범위를 구해서 해당 범위 내에 있는 모든 칸이 정답이 된다.

이렇게 하면 len(queries)만큼의 시간복잡도가 소요되므로, O(n)으로 문제를 풀 수 있다.

def solution(n, m, x, y, queries):
	#목표지점으로 범위를 초기화
    sr, sc, er, ec = x, y, x, y
    
    #역순으로 쿼리를 탐색
    for d, dx in reversed(queries):
    	#좌
        if d == 0:
        	#시작 col이 0인 경우,
            if sc == 0:
            	#끝 col의 범위를 갱신한다
                ec = min(m-1, ec+dx)
                
            #시작 col이 0이 아닌 경우,
            else:
            	#시작 col을 우측으로 dx만큼 이동한 결과가 m보다 크거나 같으면, 목표지점으로 갈 수 없기 때문에 return 0
                if sc+dx >= m: return 0
                
                #시작 col과 끝 col의 범위를 갱신한다
                sc = min(m-1, sc+dx)
                ec = min(m-1, ec+dx)
        #우        
        elif d == 1:
            #끝 col이 m-1인 경우,
            if ec == m-1:
            	#시작 col의 범위를 갱신한다
                sc = max(0, sc-dx)
                
            #끝 col이 m-1이 아닌 경우,
            else:
            	#끝 col을 좌측으로 dx만큼 이동한 결과가 0보다 작으면, 목표지점으로 갈 수 없기 때문에 return 0
                if ec-dx < 0: return 0
                
                #시작 col과 끝 col의 범위를 갱신한다
                sc = max(0, sc-dx)
                ec = max(0, ec-dx)
        #상        
        elif d == 2:
        	#시작 row가 0인 경우,
            if sr == 0:
            	#끝 row의 범위를 갱신한다
                er = min(n-1, er+dx)
                
            #시작 row가 0이 아닌 경우,
            else:
            	#시작 row를 밑으로 dx만큼 이동한 결과가 n보다 크거나 같으면, 목표지점으로 갈 수 없기 때문에 return 0
                if sr+dx >= n: return 0
                
                #시작 row와 끝 row의 범위를 갱신한다
                sr = min(n-1, sr+dx)
                er = min(n-1, er+dx)
        #하        
        else:
        	#끝 row가 n-1인 경우,
            if er == n-1:
            	#시작 row의 범위를 갱신한다
                sr = max(0, sr-dx)
            
            #끝 row가 n-1가 아닌 경우,
            else:
            	#끝 row를 위로 dx만큼 이동한 결과가 0보다 작으면, 목표지점으로 갈 수 없기 때문에 return 0
                if er+dx < 0: return 0
                
                #시작 row와 끝 row의 범위를 갱신한다
                sr = max(0, sr-dx)
                er = max(0, er-dx)
    
    
    #출발점이 될 영역의 칸 수 return
    return (er-sr+1)*(ec-sc+1)
    
#시간복잡도 = O(n), 공간복잡도 = O(n)

---

오답 노트

처음에는 모든 칸에 볼을 넣고 쿼리를 순서대로 돌아서 공을 이동시켰다.

1 <= n, m <= 10^9이기 때문에 당연히 시간초과를 예상했고, 역시나 제출해보니 1번 케이스 빼고 모두 시간초과가 났다.

from collections import deque
#좌, 우, 상, 하
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def move_ball(sx, sy, ex, ey, n, m, queries):
    x, y = sx, sy
    for cmd, d in queries:
        nx = x + dx[cmd]*d
        ny = y + dy[cmd]*d
        if nx < 0: nx = 0
        elif nx >= m: nx = m-1
        if ny < 0: ny = 0
        elif ny >= n: ny = n-1
        x, y = nx, ny
    if x == ex and y == ey: return 1
    return 0
    
def solution(n, m, x, y, queries):
    query = []
    for cmd, d in queries:
        query.append([cmd, d])
        if len(query) <= 2: continue 
        elif (query[-1][0] == 0 and query[-2][0] == 1) or (query[-1][0] == 1 and query[-2][0] == 0) or (query[-1][0] == 2 and query[-2][0] == 3) or (query[-1][0] == 3 and query[-2][0] == 2):
            d1, d2 = query[-2][1], query[-1][1]
            cmd1, cmd2 = query[-2][0], query[-1][0]
            query.pop()
            query.pop()
            if d1 > d2: query.append([cmd1, d1-d2])
            else: query.append([cmd2, d2-d1])
        
    answer = 0
    for sy in range(n):
        for sx in range(m):
            answer += move_ball(sx, sy, y, x, n, m, query)
    
    return answer