-
공 이동 시뮬레이션코딩 테스트/Level 3 2021. 10. 16. 10:28반응형
https://programmers.co.kr/learn/courses/30/lessons/87391
코딩테스트 연습 - 공 이동 시뮬레이션
n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리
programmers.co.kr
아직 프로그래머스는 파이썬 10의 패턴매칭을 지원하지 않는다.
파이썬 3.8.53.8.5 (default, Sep 8 2020, 23:06:40) [GCC 9.3.0]일단 전수조사(brute force)...
def solution(n, m, x, y, queries): answer = 0 for start_line in range(n): for start_column in range(m): if (x, y) == move(n, m, start_line, start_column, queries): answer += 1 return answer def move(n, m, line, column, queries): for direction, dx in queries: if direction == 0: column = 0 if (temp := column - dx) < 0 else temp elif direction == 1: column = m - 1 if (temp := column + dx) >= m else temp elif direction == 2: line = 0 if (temp := line - dx) < 0 else temp else: line = n - 1 if (temp := line + dx) >= n else temp return line, column결과는 당연히...
테스트 1 〉 통과 (0.02ms, 10.2MB) 테스트 2 〉 실패 (시간 초과) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (시간 초과) 테스트 6 〉 실패 (시간 초과) 테스트 7 〉 실패 (시간 초과) 테스트 8 〉 실패 (시간 초과) 테스트 9 〉 실패 (시간 초과) 테스트 10 〉 실패 (시간 초과) 테스트 11 〉 실패 (시간 초과) 테스트 12 〉 실패 (시간 초과) 테스트 13 〉 실패 (시간 초과) 테스트 14 〉 실패 (시간 초과) 테스트 15 〉 실패 (시간 초과) 테스트 16 〉 실패 (시간 초과) 테스트 17 〉 실패 (시간 초과) 테스트 18 〉 실패 (시간 초과) 테스트 19 〉 실패 (시간 초과) 테스트 20 〉 실패 (시간 초과) 테스트 21 〉 실패 (시간 초과) 테스트 22 〉 실패 (시간 초과) 테스트 23 〉 실패 (시간 초과) 테스트 24 〉 실패 (시간 초과) 테스트 25 〉 실패 (시간 초과) 테스트 26 〉 실패 (시간 초과) 테스트 27 〉 실패 (시간 초과) 테스트 28 〉 실패 (시간 초과) 테스트 29 〉 실패 (시간 초과) 테스트 30 〉 실패 (시간 초과) 테스트 31 〉 실패 (시간 초과) 테스트 32 〉 실패 (시간 초과) 테스트 33 〉 실패 (시간 초과) 테스트 34 〉 실패 (시간 초과)얄팍한 수를 시도해 봄....
깊이 우선 검색(DFS)을 응용해서...
만약 성공하면 success_paths에 경로를 저장하고,
그것과 겹치면 통과로 처리하는....
실패한 경로도 fail_paths에 저장 후 겹침 확인...def solution(n, m, x, y, queries): answer = 0 success_paths = {i: set() for i in range(len(queries))} fail_paths = {i: set() for i in range(len(queries))} for start_line in range(n): for start_column in range(m): column, line = start_column, start_line visited = {} success = False for index, (direction, dx) in enumerate(queries): if (direction, column, line) in success_paths[index]: success = True # print((direction, column, line), 'is in success_paths') break if (direction, column, line) in fail_paths[index]: # print((direction, column, line), 'is in fail_paths') break visited[index] = (direction, column, line) if direction == 0: column = 0 if (temp := column - dx) < 0 else temp elif direction == 1: column = m - 1 if (temp := column + dx) >= m else temp elif direction == 2: line = 0 if (temp := line - dx) < 0 else temp else: line = n - 1 if (temp := line + dx) >= n else temp if success is True or (x == line and y == column): answer += 1 visited_items_2_paths(visited, success_paths) # print('success_paths:', success_paths) else: visited_items_2_paths(visited, fail_paths) # print('fail_paths:', fail_paths) return answer def visited_items_2_paths(visited: dict, paths: dict): for key, value in visited.items(): paths[key].add(value)역시나 실패...
테스트 1 〉 통과 (0.06ms, 10.3MB) 테스트 2 〉 실패 (시간 초과) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (시간 초과) 테스트 6 〉 실패 (시간 초과) 테스트 7 〉 실패 (시간 초과) 테스트 8 〉 실패 (시간 초과) 테스트 9 〉 실패 (시간 초과) 테스트 10 〉 실패 (시간 초과) 테스트 11 〉 실패 (시간 초과) 테스트 12 〉 실패 (시간 초과) 테스트 13 〉 실패 (시간 초과) 테스트 14 〉 실패 (시간 초과) 테스트 15 〉 실패 (시간 초과) 테스트 16 〉 실패 (시간 초과) 테스트 17 〉 실패 (시간 초과) 테스트 18 〉 실패 (시간 초과) 테스트 19 〉 실패 (시간 초과) 테스트 20 〉 실패 (시간 초과) 테스트 21 〉 실패 (시간 초과) 테스트 22 〉 실패 (시간 초과) 테스트 23 〉 실패 (시간 초과) 테스트 24 〉 실패 (시간 초과) 테스트 25 〉 실패 (시간 초과) 테스트 26 〉 실패 (시간 초과) 테스트 27 〉 실패 (시간 초과) 테스트 28 〉 실패 (시간 초과) 테스트 29 〉 실패 (시간 초과) 테스트 30 〉 실패 (시간 초과) 테스트 31 〉 실패 (시간 초과) 테스트 32 〉 실패 (시간 초과) 테스트 33 〉 실패 (시간 초과) 테스트 34 〉 실패 (시간 초과)정공법으로 도전...
문제를 처음 봤을 때부터
도착 시점부터 역으로 거슬러 올라가는 방법을 사용해야 할 것 같은 느낌은 있었지만.
이미지를 떠올리기 어려웠습니다.공식 홈페이지의 설명과 검색을 통해 감을 잡을 수 있었습니다.
https://prgms.tistory.com/108[월간 코드 챌린지 시즌3] 10월 문제 해설
코딩이 재미있는 사람들을 위한 챌린지! 프로그래머스에서 2021년 9월 9일, 10월 7일 두 번에 걸쳐 월간 코드 챌린지 시즌3가 진행되었습니다. 2021년 10월 7일 19시 30분부터 22시 30분까지 진행된 시즌
prgms.tistory.com
일단 평평한 판위에 공을 가득 채우고,
문제에서 제시한 방향과 거리로 공을 밀어서 떨어트리는 상황을 머리 속으로 그려보고,
그걸 역으로 재생하니
경계에 멈춰져 있는 공들을 역방향으로 옮길 때 어떻게 해야하는 지 알 수 있더군요.# 0에 있는 공들은 그냥 둬야 합니다. right가 증가하면서 영역이 회복됩니다.
라고 주석을 달아두었습니다.모든 공을 다 떨어트리면 끝입니다.
if top > n - 1 or bottom < 0 or left > m - 1 or right < 0: return 0def solution(n, m, y, x, queries): top = bottom = y # n행, m열. Parameter x, y 바꿈. 행을 y로 열을 x로 맞추는 것이 익숙해서... left = right = x for direction, dx in queries[::-1]: if direction == 0: # 열 감소, 거꾸로 생각하면 열 증가 if left != 0: # 0에 있는 공들은 그냥 둬야 합니다. right가 증가하면서 영역이 회복됩니다. left += dx if left > m - 1: left = m - 1 right += dx if right > m - 1: right = m - 1 elif direction == 1: # 열 증가, 거꾸로 생각하면 열 감소 left -= dx if left < 0: left = 0 if right != m - 1: right -= dx if right < 0: right = 0 elif direction == 2: # 행 감소, 거꾸로 생각하면 행 증가 if top != 0: top += dx if top > n - 1: top = n - 1 bottom += dx if bottom > n - 1: bottom = n - 1 elif direction == 3: # 행 증가, 거꾸로 생각하면 행 감소 top -= dx if top < 0: top = 0 if bottom != n - 1: bottom -= dx if bottom < 0: top = 0 if top > n - 1 or bottom < 0 or left > m - 1 or right < 0: return 0 return (bottom - top + 1) * (right - left + 1)테스트 1 〉 통과 (0.00ms, 10.3MB) 테스트 2 〉 통과 (0.28ms, 10.3MB) 테스트 3 〉 통과 (0.32ms, 10.3MB) 테스트 4 〉 통과 (0.30ms, 10.3MB) 테스트 5 〉 통과 (30.00ms, 21.8MB) 테스트 6 〉 통과 (62.74ms, 34.6MB) 테스트 7 〉 통과 (44.16ms, 28.5MB) 테스트 8 〉 통과 (44.81ms, 28.4MB) 테스트 9 〉 통과 (44.80ms, 29.3MB) 테스트 10 〉 통과 (40.49ms, 26.3MB) 테스트 11 〉 통과 (36.79ms, 23.7MB) 테스트 12 〉 통과 (40.25ms, 28.6MB) 테스트 13 〉 통과 (51.10ms, 28.6MB) 테스트 14 〉 통과 (54.97ms, 29.2MB) 테스트 15 〉 통과 (65.05ms, 34.5MB) 테스트 16 〉 통과 (61.87ms, 34.6MB) 테스트 17 〉 통과 (59.90ms, 34.6MB) 테스트 18 〉 통과 (56.85ms, 34.6MB) 테스트 19 〉 통과 (58.83ms, 34.5MB) 테스트 20 〉 통과 (62.59ms, 34.5MB) 테스트 21 〉 통과 (62.65ms, 34.6MB) 테스트 22 〉 통과 (60.16ms, 34.5MB) 테스트 23 〉 통과 (59.99ms, 34.6MB) 테스트 24 〉 통과 (58.78ms, 34.5MB) 테스트 25 〉 통과 (0.28ms, 10.4MB) 테스트 26 〉 통과 (1.04ms, 10.5MB) 테스트 27 〉 통과 (0.51ms, 10.4MB) 테스트 28 〉 통과 (0.04ms, 10.3MB) 테스트 29 〉 통과 (0.24ms, 10.3MB) 테스트 30 〉 통과 (0.12ms, 10.3MB) 테스트 31 〉 통과 (0.12ms, 10.3MB) 테스트 32 〉 통과 (1.66ms, 10.7MB) 테스트 33 〉 통과 (3.49ms, 33.3MB) 테스트 34 〉 통과 (2.42ms, 22.9MB)이렇게까지만 작성해도 통과군요....
def solution(n, m, y, x, queries): top = bottom = y # n행, m열. Parameter x, y 바꿈. 행을 y로 열을 x로 맞추는 것이 익숙해서... left = right = x for direction, dx in queries[::-1]: if direction == 0: # 열 감소, 거꾸로 생각하면 열 증가 if left != 0: left += dx if left > m - 1: left = m - 1 right += dx if right > m - 1: right = m - 1 elif direction == 1: # 열 증가, 거꾸로 생각하면 열 감소 left -= dx if left < 0: left = 0 if right != m - 1: right -= dx if right < 0: right = 0 elif direction == 2: # 행 감소, 거꾸로 생각하면 행 증가 if top != 0: top += dx if top > n - 1: top = n - 1 bottom += dx if bottom > n - 1: bottom = n - 1 elif direction == 3: # 행 증가, 거꾸로 생각하면 행 감소 top -= dx if top < 0: top = 0 if bottom != n - 1: bottom -= dx if bottom < 0: top = 0 if top > n - 1 or bottom < 0 or left > m - 1 or right < 0: return 0 return (bottom - top + 1) * (right - left + 1)테스트 1 〉 통과 (0.00ms, 10.4MB) 테스트 2 〉 통과 (0.26ms, 10.3MB) 테스트 3 〉 통과 (0.28ms, 10.3MB) 테스트 4 〉 통과 (0.44ms, 10.3MB) 테스트 5 〉 통과 (27.79ms, 21.9MB) 테스트 6 〉 통과 (56.45ms, 34.7MB) 테스트 7 〉 통과 (42.86ms, 28.6MB) 테스트 8 〉 통과 (38.58ms, 28.5MB) 테스트 9 〉 통과 (43.12ms, 29.2MB) 테스트 10 〉 통과 (33.59ms, 26.2MB) 테스트 11 〉 통과 (31.60ms, 23.8MB) 테스트 12 〉 통과 (40.04ms, 28.4MB) 테스트 13 〉 통과 (44.92ms, 28.4MB) 테스트 14 〉 통과 (49.06ms, 29.2MB) 테스트 15 〉 통과 (60.99ms, 34.5MB) 테스트 16 〉 통과 (51.89ms, 34.5MB) 테스트 17 〉 통과 (54.83ms, 34.6MB) 테스트 18 〉 통과 (57.75ms, 34.5MB) 테스트 19 〉 통과 (66.55ms, 34.5MB) 테스트 20 〉 통과 (56.08ms, 34.6MB) 테스트 21 〉 통과 (56.58ms, 34.5MB) 테스트 22 〉 통과 (55.63ms, 34.6MB) 테스트 23 〉 통과 (53.79ms, 34.6MB) 테스트 24 〉 통과 (51.21ms, 34.6MB) 테스트 25 〉 통과 (0.23ms, 10.3MB) 테스트 26 〉 통과 (0.94ms, 10.5MB) 테스트 27 〉 통과 (0.44ms, 10.4MB) 테스트 28 〉 통과 (0.04ms, 10.3MB) 테스트 29 〉 통과 (0.21ms, 10.3MB) 테스트 30 〉 통과 (0.22ms, 10.3MB) 테스트 31 〉 통과 (0.10ms, 10.3MB) 테스트 32 〉 통과 (1.39ms, 10.8MB) 테스트 33 〉 통과 (3.66ms, 33.3MB) 테스트 34 〉 통과 (1.14ms, 22.9MB)반응형