99클럽 코테 스터디 27일차 TIL, 프로그래머스 / 공 이동 시뮬레이션

🔑 오늘의 학습 키워드 : 구현

🔗 문제링크  https://school.programmers.co.kr/learn/courses/30/lessons/87391

 

def solution(n, m, goal_x, goal_y, queries):
    # 초기화
    min_x, max_x = goal_x, goal_x
    min_y, max_y = goal_y, goal_y
        
    for command, length in queries[::-1]:
        if command == 0:
            max_y = min(m - 1, max_y + length)
            if min_y > 0:
                min_y += length
        elif command == 1:
            min_y = max(0, min_y - length)
            if max_y < m - 1:
                max_y -= length
        elif command == 2:
            max_x = min(n - 1, max_x + length)
            if min_x > 0:
                min_x += length
        elif command == 3:
            min_x = max(0, min_x - length)
            if max_x < n - 1:
                max_x -= length        
        # 범위를 벗어나면 목표 지점에 도달할 수 없음
        if min_x >= n or max_x < 0 or min_y >= m or max_y < 0:
            return 0
            
    return (max_x - min_x + 1) * (max_y - min_y + 1)

 

🗒️ 공부한 내용 본인의 언어로 정리하기

😎 풀이 회고

(wrong) 틀린 풀이 (의식의 흐름대로 풀었는데 시간초과)

def solution(n, m, goal_x, goal_y, queries):
    answer = 0
    
    directions = [(0,-1),(0,1),(-1,0),(1,0)] 
    grid = [[0]*m for _ in range (n)]
    
    def in_range (x,y):
        return 0<=x<n and 0<=y<m
    
    # 시작점(x,y) -> 시작점에 도착하는지 bool 
    def move(x,y):
        for direct_idx, length in queries:
            dx, dy = directions[direct_idx]
            nx , ny = x + dx * length , y + dy * length
            if in_range(nx,ny):
                x,y = nx,ny
        return (goal_x, goal_y) == (x,y)
    
    for i in range (n):
        for j in range (m):
            if move(i,j):
                answer += 1
    
    return answer

-> 도착점부터 시작하면 될라나?

 

(wrong) 도착점부터 시작해서 역순으로 가는 풀이

from collections import deque

 

def solution(n, m, goal_x, goal_y, queries):

    answer = 0

    

    # directions = [(0,-1),(0,1),(-1,0),(1,0)] 

    reverse_directions = [(0,1),(0,-1),(1,0),(-1,0)] 

    

    def in_range (x,y):

        return 0<=x<n and 0<=y<m

    

    def reverse_move():

        able_spot = set([(goal_x,goal_y)])

        for command, length in queries[::-1]:

            dx, dy = reverse_directions[command]

            tmp = set()

            while able_spot:

                x,y = able_spot.pop()

                before_x , before_y = x + dx * length , y + dy * length

                if in_range(before_x,before_y):

                    tmp.add((before_x,before_y))

                if not in_range (x - dx * length , y - dy * length):

                    tmp.add((x, y ))

            able_spot = tmp

        return len(able_spot)

    

    return reverse_move()

-> 마찬가지로 시간 초과

-> 문제 다시 확인

-> 가로막히는 경우 해당 끝점까지 되는 것이었음

ex) 5x5에서 3,3 점에서 위로 5만큼 가면 0,3, 1,3,  2,3,  3,3이 후보가 될 수 있는 것

 

=> 그렇다면 x,y범위로 해서 구하면 되겠다

def solution(n, m, goal_x, goal_y, queries):
    # 초기화
    min_x, max_x = goal_x, goal_x
    min_y, max_y = goal_y, goal_y
    
    reverse_directions = [(0,1),(0,-1),(1,0),(-1,0)]
    
    for command, length in queries[::-1]:
        dx, dy = reverse_directions[command]

        if dx == 1:
            max_x = min(n - 1, max_x + length)
            if min_x > 0:
                min_x += length
        elif dx == -1:
            min_x = max(0, min_x - length)
            if max_x < n - 1:
                max_x -= length
        elif dy == 1:
            max_y = min(m - 1, max_y + length)
            if min_y > 0:
                min_y += length
        elif dy == -1:
            min_y = max(0, min_y - length)
            if max_y < m - 1:
                max_y -= length
        
        # 범위를 벗어나면 목표 지점에 도달할 수 없음
        if min_x >= n or max_x < 0 or min_y >= m or max_y < 0:
            return 0
            
    return (max_x - min_x + 1) * (max_y - min_y + 1)

✅ 오늘의 회고

- 완전 탐색에서 시간 초과가 발생하면 역순을 떠올림

- 문제를 똑바로 읽자;

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL