[프로그래머스 코딩테스트 연습] 공 이동 시뮬레이션 - python3

개요

난이도 level 3

문제

문제 설명

n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.

• 열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
• 열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
• 행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
• 행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))

단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다. 예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때 query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다. (격자의 크기가 5행 × 4열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)

격자의 행의 개수 n, 열의 개수 m, 정수 x와 y, 그리고 쿼리들의 목록을 나타내는 2차원 정수 배열 queries가 매개변수로 주어집니다. n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 queries 내의 쿼리들을 순서대로 시뮬레이션했을 때, x행 y열에 도착하는 시작점의 개수를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ n ≤ 109
• 1 ≤ m ≤ 109
• 0 ≤ x < n
• 0 ≤ y < m
• 1 ≤ queries의 행의 개수 ≤ 200,000
  • queries의 각 행은 [command,dx] 두 정수로 이루어져 있습니다.
  • 0 ≤ command ≤ 3
  • 1 ≤ dx ≤ 109
  • 이는 query(command, dx)를 의미합니다.

---

입출력 예nmxyqueriesresult

2	2	0	0	[[2,1],[0,1],[1,1],[0,1],[2,1]]	4
2	5	0	1	[[3,1],[2,2],[1,1],[2,3],[0,1],[2,1]]	2

---

입출력 예 설명

입출력 예 #1

• 다음 애니메이션은 4개의 가능한 시작점에 대한 모든 시뮬레이션을 나타낸 것입니다.

• 어떤 곳에서 출발하더라도 항상 0행 0열에 도착하기 때문에, 4를 return 해야 합니다.

입출력 예 #2

• 다음 애니메이션은 10개의 가능한 시작점에 대한 모든 시뮬레이션을 나타낸 것입니다.

• 0행 1열, 1행 1열에서 출발했을 때만 0행 1열에 도착하므로, 2를 return 해야 합니다.

풀이

def solution(n, m, x, y, queries):
    # n, x 행, 2 : x감소, 3 : x증가
    # m, y 열, 0 : y감소, 1 : y증가
    maxx, maxy = x, y
    minx, miny = x, y
    
    for qq in reversed(queries) :
        ar, dx = qq
        if ar == 0 : # 0 : y감소
            if miny == 0 :
                maxy = maxy + dx if maxy + dx < m else m - 1
            else :
                miny = miny + dx if miny + dx < m else m - 1
                maxy = maxy + dx if maxy + dx < m else m - 1
        if ar == 1 : # 1 : y증가
            if maxy == m - 1 :
                miny = miny - dx if miny - dx >= 0 else 0
            else :
                maxy = maxy - dx if maxy - dx >= 0 else 0
                miny = miny - dx if miny - dx >= 0 else 0
        if ar == 2 : # 2 : x감소
            if minx == 0 :
                maxx = maxx + dx if maxx + dx < n else n - 1
            else :
                minx = minx + dx if minx + dx < n else n - 1
                maxx = maxx + dx if maxx + dx < n else n - 1
        if ar == 3 : # 3 : x증가
            if maxx == n - 1 :
                minx = minx - dx if minx - dx >= 0 else 0
            else :
                maxx = maxx - dx if maxx - dx >= 0 else 0
                minx = minx - dx if minx - dx >= 0 else 0
        
    # 시작점이 존재하지 않을 경우를 위한 검산
    xx, yy = minx, miny
    for qq in queries :
        ar, dx = qq
        if ar == 0 : # 0 : y감소
            yy = yy - dx if yy - dx >=0 else 0
        if ar == 1 : # 1 : y증가
            yy = yy + dx if yy + dx < m else m - 1
        if ar == 2 : # 2 : x감소
            xx = xx - dx if xx - dx >=0 else 0
        if ar == 3 : # 3 : x증가
            xx = xx + dx if xx + dx < n else n - 1
    return (maxx - minx + 1) * (maxy - miny + 1)  if (x == xx) and (y == yy) else 0

느낀점

시뮬레이션 유형을 풀어보려고 찾아본 문제인데

아.. 이번문제 어려웠다!

 

처음엔 그냥 정석대로 시뮬레이션해서 풀었다 (밑에 코드있음)

그런데 당연히 시간 초과돼버림.. (대부분 시간초과돼서 14점인가 나옴)

 

질문하기를 슬쩍보니 범위만을 구해서 한다는듯

그래서 좀 따라해봤는데

마지막 테스트케이스 33이랑 34가 실패인 것이다

그래서 다시 보니 아예 시작점이 존재하지 않는 경우도 존재했다..

 

그래서 어거지로 넣은 코드가 검산..

시간은 2배로 걸리고;; 

저게 최선은 아닐듯한데 계산하기가 복잡하다고 생각이 들었음 ㅜ

 

여튼 이렇게 한문제 넘긴다..

 

근데 이거 정말 케이스 다 안알려주면 걍 제출해버릴거같음 ㅜ

 

 

 

효율안따지고 정석으로 풀려고했던 흔적 남기고갑니다,,

def solution(n, m, x, y, queries):
    # n, x 행, 2 : x감소, 3 : x증가
    # m, y 열, 0 : y감소, 1 : y증가
    able = set([(x,y)])
    for qq in reversed(queries) :
        ar, dx = qq
        temp = set()
        if ar == 0 :
            for aa in able :
                xx, yy = aa
                # y를 1만큼 감소했고 위치는 1 0, 0 0
                # 최대 1 1 임
                # 이전 위치는 0 0 또는 1 0
                if yy == 0 :
                    for ddxx in range(dx+1):
                        temp.add((xx,yy+ddxx if yy+ddxx<m else m - 1))
                else :
                    temp.add((xx,yy+dx if yy+dx<m else m - 1))
        if ar == 1 :
            for aa in able :
                xx, yy = aa
                # y를 1만큼 증가했고 위치는 1 0, 0 0, 1 1 , 0 1
                # 최대 1 1 임
                # 이전 위치는 0 0 또는 1 0
                if yy == m-1 :
                    for ddxx in range(dx+1):
                        temp.add((xx,yy-ddxx if yy-ddxx>=0 else 0))
                else :
                    temp.add((xx,yy-dx if yy-dx>=0 else 0))
        if ar == 2 :
            for aa in able :
                xx, yy = aa
                # x를 1만큼 감소했고 위치는 0 0
                # 최대 1 1 임
                # 이전 위치는 0 0 또는 1 0
                if xx == 0 :
                    for ddxx in range(dx+1):
                        temp.add((xx+ddxx if xx+ddxx<n else n - 1,yy))
                else :
                    temp.add((xx+dx if xx+dx<n else n - 1,yy))
        if ar == 3 :
            for aa in able :
                xx, yy = aa
                # x를 1만큼 증가했고 위치는 1 0, 0 0, 1 1 , 0 1
                # 최대 1 1 임
                # 이전 위치는 0 0 또는 1 0
                if xx == n-1 :
                    for ddxx in range(dx+1):
                        temp.add((xx-ddxx if xx-ddxx>=0 else 0,yy))
                else :
                    temp.add((xx-dx if xx-dx>=0 else 0,yy))
        able = temp
    print(able)
    return len(able)