문제

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

나의 코드 (답안참조)

"""
1. 아이디어
집합 자료형과 방향 벡터를 이용하면 쉽게 풀 수 있는 문제이다.

2. 시간복잡도
o(n)
"""

def solution(dirs):
    
    answer = 0
    visited = set()
    x, y = 0, 0
    
    dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
    d = {'U':0, 'L':1, 'D':2, 'R':3}
    
    for dir in dirs:
        i = d[dir]
        nx, ny = x + dx[i], y + dy[i]
        
        if nx < -5 or nx > 5 or ny < -5 or ny > 5:
            continue
        
        if (x, y, nx, ny) not in visited:
            visited.add((x, y, nx, ny))
            visited.add((nx, ny, x, y)) # 길은 '양방향'
            answer += 1
        
        x, y = nx, ny
    
    return answer
    

다시 풀이한 코드

• 동그라미 친 부분의 위치를 주의 해야 한다. 처음에는 두번째 if문 안에 넣었는데 통과가 안되서 다시 보니 좌표 갱신은 범위를 벗어나지 않는 이상 항상 해줘야 하기 때문에 첫번째 if문에 넣는게 맞다. 두번째 if문에서 좌표 갱신을 하게 되면 방문한 적이 없을때만 좌표 갱신이 되기 때문에 틀리게 되는 것이다.

또 다시 풀이한 코드

• 굳이 집합 자료형일 필요는 없다.

그냥 길은 양방향이기 때문에
visited.append((x, y, mx, my))
visited.append((mx, my, x, y))
이게 중요할 뿐

def solution(dirs):
    
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    d = {'U':0, 'D':1, 'L':2, 'R':3}
    visited = []
    x, y = 0, 0
    answer = 0
    
    for dir in dirs:
        
        mx = x + dx[d[dir]]
        my = y + dy[d[dir]]
        
        if mx < -5 or mx > 5 or my < -5 or my > 5:
            continue
        
        if (x, y, mx, my) not in visited:
            visited.append((x, y, mx, my))
            visited.append((mx, my, x, y))
            answer += 1
        
        x, y = mx, my
        
    return answer
        

느낀점

방향벡터 많이 풀어보기..