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

0. 문제 링크

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

프로그래머스

 

1. 문제 설명

1) 주어진 queries에서 direction과 distance만큼 공을 움직여서 x, y에 도달하는지 확인

 

2. 입출력

# input
n = 2
m = 2
x = 0
y = 0
queries = [[2,1],[0,1],[1,1],[0,1],[2,1]]

# output
result = 4

 

3. 코드

def solution(n, m, x, y, queries):
    answer = 0

    row_start, row_end, col_start, col_end = x, x, y, y

    for i in range(len(queries)-1, -1, -1):                                     # queries-1 개까지 거꾸로 반복
        direction, distance = queries[i]                                        # 방향, 거리 변수에 저장

        if direction == 0:                                                      # 열 증가 시켜보기
            col_end += distance                                                 # col_end 늘리기
            if col_end > m-1:                                                   # 범위를 벗어나면
                col_end = m-1                                                   # 끝 값으로
            if col_start != 0:                                                  # col_start가 0이 아니라면
                col_start += distance                                           # col_start도 늘리기
        
        elif direction == 1:                                                    # 열 감소 시켜보기
            col_start -= distance                                               # col_start 줄이기
            if col_start < 0:                                                   # 범위를 벗어나면
                col_start = 0                                                   # 0으로
            if col_end != m-1:                                                  # col_end가 끝 값이 아니라면
                col_end -= distance                                             # col_end도 줄이기

        elif direction == 2:                                                    # 행 증가 시켜보기
            row_end += distance                                                 # row_end 늘리기
            if row_end > n-1:                                                   # 범위를 벗어나면
                row_end = n-1                                                   # 끝 값으로
            if row_start != 0:                                                  # row_start가 0이 아니라면
                row_start += distance                                           # row_start도 늘리기
        
        else:                                                                   # 행 감소 시켜보기
            row_start -= distance                                               # row_start 줄이기
            if row_start < 0:                                                   # 범위를 벗어나면
                row_start = 0                                                   # 0으로
            if row_end != n-1:                                                  # row_end가 끝 값이 아니라면
                row_end -= distance                                             # row_end도 줄이기
        
        if row_start > n-1 or row_end < 0 or col_start > m-1 or col_end < 0:    # 쿼리 중 범위를 벗어나면
            return answer                                                       # answer만 return
    
    answer = (row_end - row_start + 1) * (col_end - col_start + 1)              # answer 계산

    return answer

 

실행 결과

 

4. 회고

n x m의 모든 경우의 수에서 queries가 가능한지를 계산하는 삼중 for 문으로 작성하였는데, 시간 초과가 떴다. 다른 방법을 모색하다가 반대로 queries에서 가능한 경우의 수를 따져보는 방법을 찾게 되었다. 이 방법을 사용하면 queries만큼만 계산하면 되서 시간 복잡도가 상당히 많이 줄어든다.

처음에는 다른 코드를 참고하면서 푸느라 변수명을 left, right, top, bottom으로 정했는데, 행과 열을 생각하려니 헷갈리는 요소들이 많았다. 차라리 row_start, row_end, col_start, col_end와 같이 지었을 때 덜 헷갈릴 수 있었다.

Level3는 확실히 어렵다...

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Programmers/ball_simulation.py

GitHub - iihye/Algorithm