처음엔 11*11 해서 해당 좌표를 visited T/F로 설정했는데 생각해보니 한 칸 당 총 4개의 길이 있기 때문에 그냥 visited를 길 그대로 넣고 in/not in으로 풀자는 생각을 했음
4개의 길이 있으므로 (현재 좌표 + 갈 좌표)해서 visited에 넣고 갔던 길을 체크하는 것은 좋았으나 반대방향에서 걸어오는 것을 체크하지 않았음 바보!!! (가장 쉬운 반례 UDU=1)
📖풀이
📎구현
def solution(dirs): dir = {'U':(0, 1), 'D':(0, -1), 'R':(1, 0), 'L':(-1, 0)} n = 5 fst = 0 x, y = 0, 0 visited = set() for d in dirs: d1, d2 = dir[d] if x+d1>=-n and y+d2>=-n and x+d1<=n and y+d2 <=n: px, py = x, y x += d1 y += d2 if (px, py, x, y) not in visited: fst += 1 visited.add((px, py, x, y)) visited.add((x, y, px, py)) return fst
📖What I learned
visited 탐색 시간 줄이기 위해선 list가 아니라 set을 염두에 두자! 여기선 디렉션 최대가 500이라서 시간복잡도 문제는 없었지만 set으로 선언할 시 눈에 띄는 수행 시간 감소)
이미 방문한 길을 반대 방향에서 걸어온다고 다른 길이 아니다! 디테일함을 체크하자 제발!!!!(UDU = 1)