[프로그래머스]캐릭터의 좌표

[69] 캐릭터의 좌표

책 구매하기

문제 정보

• 분류: 시뮬레이션
• 정답률: 75%
• 권장 시간 복잡도: O(M)
• 핵심 키워드: 좌표 이동, 경계 체크, 명령 처리, 시뮬레이션
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/120861

문제를 읽을 때 체크할 포인트

보드 바깥으로 나가는 이동만 막으면 되는 단순 시뮬레이션 문제다. 현재 좌표를 갱신하기 전에 다음 좌표가 경계 안인지 먼저 확인하면 된다.

규칙을 그대로 따라가는 문제처럼 보여도 상태를 어떻게 단순하게 들고 갈지가 더 중요하다. 좌표나 값의 변화만 깔끔하게 관리하면 의외로 짧게 끝난다.

풀이 흐름

1. 현재 좌표를 (0,0)에서 시작한다.
2. 명령 하나마다 dx, dy를 적용한 다음 좌표를 계산한다.
3. 보드 범위 안이면 좌표를 갱신하고, 아니면 무시한다.

구현할 때 놓치기 쉬운 부분

한 칸 움직이기 전에 다음 좌표가 보드 범위를 넘는지 먼저 확인해야 한다. 좌표를 먼저 바꾸고 나중에 되돌리는 방식은 구현만 복잡해진다.

파이썬 정답 코드

def solution(keyinput, board):
  # 현재 좌표를 (0,0)에서 시작한다.
  x = y = 0
  max_x = board[0] // 2
  max_y = board[1] // 2

  move = {
    "left": (-1, 0),
    "right": (1, 0),
    "up": (0, 1),
    "down": (0, -1),
  }

  # 명령 하나마다 dx, dy를 적용한 다음 좌표를 계산한다.
  for cmd in keyinput:
    # 보드 범위 안이면 좌표를 갱신하고, 아니면 무시한다.
    dx, dy = move[cmd]
    nx, ny = x + dx, y + dy
    if -max_x <= nx <= max_x and -max_y <= ny <= max_y:
      x, y = nx, ny

  return [x, y]

시간 복잡도

M은 keyinput의 길이이다.

명령이나 입력 항목 M개를 순서대로 처리하는 구조이다. 각 단계에서 비교와 갱신만 하고, 항목 하나를 다시 크게 되돌아보지 않으므로 선형으로 끝난다.

따라서 시간 복잡도는 O(M)이다.