[Python] 프로그래머스 - 방문 길이 (Lv. 2)

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

프로그래머스

 

틀린 풀이

def solution(dirs):
    answer = set()  # 처음 걸어본 길 --> 중복 제거하기 위해 자료형은 set를 활용
    dirs = list(dirs)
    x, y = 0, 0
    
    for dir in dirs:
        cur_x, cur_y = x, y
        if dir == "U":
            y += 1
        elif dir == "L":
            x -= 1
        elif dir == "R":
            x += 1
        else:
            y -= 1
            
        if not (-5<=x<=5 and -5<=y<=5):  # 좌표를 벗어나는 곳은 무시해야하니까 이전으로 롤백
            x, y = cur_x, cur_y
        else:
            answer.add((cur_x, cur_y, x, y))

    return len(answer)

 

1) answer.add((cur_x, cur_y, x, y))가 틀린 이유

우리가 구하고자 하는것은 '방문 좌표'가 아니라 '방문 길이' 이므로, (0, 5)에서 (5, 5)로 가는 것과 (5, 5)에서 (5,0)로 가는 것은 서로 같은 구간을 거치는 것이다.

따라서 아래와 같이 양쪽 모두 추가 후 2로 나누면 거쳐간 길이를 중복 없이 더할 수 있다.

        if not (-5<=x<=5 and -5<=y<=5):  # 좌표를 벗어나는 곳은 무시해야하니까 이전으로 롤백
            x, y = cur_x, cur_y
        else:
            answer.add((cur_x, cur_y, x, y))
            answer.add((x, y, cur_x, cur_y))

    return len(answer) / 2

 

 

맞는 풀이

def solution(dirs):
    answer = set()
    dirs = list(dirs)
    x, y = 0, 0   # 초기좌표 --> (0, 0)
    
    for dir in dirs:
        cur_x, cur_y = x, y
        if dir == "U":
            y += 1
        elif dir == "L":
            x -= 1
        elif dir == "R":
            x += 1
        else:
            y -= 1
            
        if not (-5<=x<=5 and -5<=y<=5):   # 좌표를 벗어나면 롤백
            x, y = cur_x, cur_y
        else:
            answer.add((cur_x, cur_y, x, y))  # (0, 5) (5, 5) // (5, 5) (0, 5)는 동일하므로 모두 포함시켜야함
            answer.add((x, y, cur_x, cur_y))

    return len(answer)/2

 

다른사람 풀이

def solution(dirs):
    s = set()
    d = {'U': (0,1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)}
    # 좌표를 위와 같이 배열 / 딕셔너리 형태로 관리하면 편함
    x, y = 0, 0
    for i in dirs:
        nx, ny = x + d[i][0], y + d[i][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:  # 좌표에 해당할때만 이전 좌표와 전진한 좌표를 모두 더해줌 --> 해당하지 않는 부분은 무시하므로 굳이 더할 필요가 없음
            s.add((x,y,nx,ny))
            s.add((nx,ny,x,y))
            x, y = nx, ny    # 전진
    return len(s)//2