[프로그래머스] 예상 대진표, 공원 산책 - Python

• 예상 대진표

import math

def solution(n,a,b):
    answer = 0
    while a != b:
        a = math.ceil(a/2)
        b = math.ceil(b/2)
        answer += 1
    return answer

👀 시간 복잡도 O(log(max(a, b)))

• 공원 산책

def find_direction(d):
    if d == "N":
        return 0
    elif d == "S":
        return 1
    elif d == "W":
        return 2
    elif d == "E":
        return 3

# 공원, 로봇강아지가 수행할 명령이 담긴 문자열 배열
def solution(park, routes):
    w = len(park[0])
    h = len(park)

    # 시작점 찾기
    for i in range(h):
        for j in range(w):
            if park[i][j] == 'S':
                answer = [i, j]

    # 북, 남, 서, 동
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while routes:
        stop = False
        d, steps = routes.pop(0).split(' ')

        # 앞으로 가는 동안 내내
        for j in range(1, int(steps) + 1):
            nx = answer[0] + (j * dx[find_direction(d)])
            ny = answer[1] + (j * dy[find_direction(d)])

            if nx < 0 or ny < 0 or nx >= h or ny >= w or park[nx][ny] == "X":
                stop = True
                break

        if stop:
            continue

        answer = [nx, ny]
    # [세로 방향 좌표, 가로 방향 좌표]순
    return answer

dx, dy를 분리하지 않고 같이 [x, y]를 같이 쓰는 방법도 있다.
nx가 h의 범위, ny가 w의 범위라는 점을 유의해야 한다.
해당 steps만큼 이동하면서 장애물을 한 개라도 만나면 stop해야 한다. (해당 목적지로 이동 불가능)

👀 시간 복잡도 O(W * H) + O(M)
M은 routes 배열의 길이
W, H, M은 각각 최대 50이므로, 전체 시간 복잡도는 O(50 * 50) + O(50)
O(2500) + O(50)이므로, 최종적으로 전체 시간 복잡도는 O(1) + O(1) -> O(1)

문제를 풀 때 조건을 제대로 살피지 못해 오래 걸렸다. 꼼꼼히 살피자.