[PS, Algorithm] - 방문 길이 (코딩테스트 연습, LEVEL 2)

📒문제

📌풀이

from collections import defaultdict

def solution(dirs):
    def move(cur_x, cur_y, dir):
        new_x, new_y = 0, 0
        
        if dir == 'L':
            new_x = cur_x - 1
            new_y = cur_y
        elif dir == 'U':
            new_x = cur_x
            new_y = cur_y + 1
        elif dir == 'R':
            new_x = cur_x + 1
            new_y = cur_y
        elif dir == 'D':
            new_x = cur_x
            new_y = cur_y - 1
            
        return new_x, new_y
    
    visit = defaultdict(list)
    cur_x, cur_y = 0, 0
    
    result = 0
    for dir in dirs:
        new_x, new_y = move(cur_x, cur_y, dir)
        
        if -5 <= new_x <= 5 and -5 <= new_y <= 5:
            if (new_x, new_y) not in visit[(cur_x, cur_y)]: #새로운 길일때
                result += 1
                visit[(cur_x, cur_y)].append((new_x, new_y))
                visit[(new_x, new_y)].append((cur_x, cur_y))
                
            cur_x, cur_y = new_x, new_y
    
    return result               

처음에 최적화를 해야 되나 고민했었는데 dirs길이가 500이하라서 딱히 최적화를 안 해도 상관없겠다는 생각이 들었다. 그냥 출발점과 도착점을 dict 자료에 넣어주고 지나간 길인지 지나가지 않은 길인지 확인해 주었다.

📢주의해야 했던 점
이 길들은 단방향 길이 아니라 양방향 길이므로, 출발점을 key로, 도착점을 value로 dict에 넣어줬다면 그때 도착점을 key로, 출발점을 value로 하는 것도 dict에 똑같이 넣어줘야 한다.

📌모범 풀이

처음에 set를 쓸까 고민도 했다가 그냥 dict를 썼는데, 모범풀이를 보니 set를 통해 굉장히 간결하게 풀었다.

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

여기서 얻어가야 할 점이 있다면 방향 전환 부분을 굳이 조건문 나눠가며 할 필요 없이 dict를 통해 간단하게 구현 가능하다는 점과, set 이 두가지 부분이 있겠다. 저기서 len(s)//2로 나누는 이유는 길을 양방향으로 표현하기 위해 출발점->도착점, 도착점->출발점의 형태로 넣어놓았기 때문이다.