[Programmers] - 방문 길이 (Summer/Winter Coding(~2018)) with Python

📎 간략한 문제 정리

• 좌표평면상의 점 이동을 추적하여 이동 거리를 계산하는 문제입니다. 단 이동 루트가 중첩되는 경우 한 개의 이동거리만 계산합니다.

📈 문제 분석

• 조심해야할 부분은 좌표평면의 사이즈가 정해져 있는 점입니다. 정해진 범위를 벗어나는 이동 명령은 아예 무시합니다. 포인트는 이동한 위치를 체크하는 것인데 시작점과 끝점을 묶은 튜플로 표현할 수 있습니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 겹치는 부분을 제거하기 위해 여러가지 방법이 있을 수 있습니다. x좌표, y좌표가 더 작은 점을 왼쪽 기준점으로 두어 검색하여 존재 여부를 확인하고 추가할 수 있지만 이렇게 sort를 하게되면 O(N)이므로 비효율적입니다. Dictionary를 사용할 수 있지만 기준을 맞추기 위해서는 결국 sort를 해야합니다. Dictionary는 중복이 없는 key만 가질 수 있고 한 기준점은 여러 점으로 이동할 수 있기 때문입니다. 그래서 Set을 사용하여 중복을 제거하겠습니다.

💻 풀이한 코드

def solution(dirs):
    trace = set()
    x, y = 0, 0
    for dir in dirs:
        temp_xy = (x, y)
        if dir == "U" and -5 <= y < 5:
            y += 1
        elif dir == "D" and -5 < y <= 5:
            y -= 1
        elif dir == "R" and -5 <= x < 5:
            x += 1
        elif dir == "L" and -5 < x <= 5:
            x -= 1
        if temp_xy != (x, y):
            trace.add((temp_xy, (x, y)))
            trace.add(((x, y), temp_xy))
    return len(trace)//2

📝 해결 과정에서 만난 문제, 고민들

• 시작점과 끝점의 위치를 조절하여 추가하려면 결국 sort를 사용해야합니다. 그래서 시작점과 도착점을 넣을 때 양 방향을 모두 넣어준 후 결과를 2로 나눕니다. 방향이 없는 연결일 경우 방향을 만들어서 자료를 담을 수도 있지만 양방향을 모두 넣고 2를 나눠주는 로직도 가능합니다.
• 시작점과 도착점이 같을 경우 선이 아니라 점이므로 체크해줘야합니다.
• 문제에 보이지 않는 조건이 많습니다. 문제를 해석하며 조건을 생각할 수 있다면 좋겠지만 만약에 생각하지 못한다면 반례를 통해 유추할 필요가 있습니다.

https://programmers.co.kr/learn/courses/30/lessons/49994