프로그래머스Summer/Winter Coding(~2018) 방문 길이
문제 설명
https://programmers.co.kr/learn/courses/30/lessons/49994
답안
나의 풀이
function solution(dirs) {
let from = { x: 0, y: 0 };
const dirInfo = {
U: { direction: "y", value: 1 },
D: { direction: "y", value: -1 },
R: { direction: "x", value: 1 },
L: { direction: "x", value: -1 },
};
const visit = new Set();
for (const dir of dirs) {
const { direction, value } = dirInfo[dir];
const newValue = from[direction] + value;
if (newValue > 5 || newValue < -5) continue;
const to = { ...from };
to[direction] = newValue;
visit.add("" + from.x + from.y + to.x + to.y);
visit.add("" + to.x + to.y + from.x + from.y);
from = to;
}
return visit.size / 2;
}
시간복잡도: O(N)
- 움직인 직석을 표현하기 위해 from과 to에 시작점과 도착점을 표시한다.
- dirs에 반복문을 돌며 한글자씩 움직이는 방향을 visit라는 Set에 추가한다.
중복으로 갔던 길은 개수를 세면 안되기 때문에 Set을 사용 - newValue에 기존에 x 또는 y의 좌표에 움직이려는 값(1 또는 -1) 을 더해 저정한다.
- 좌표들이 -5 ~ 5 사이에 있어야 하므로 newValue가 해당 범위를 벗어나면 Set에 추가하지 않고 continue한다.
- to에 from을 복사하고 newValue로 업데이트 해준다.
-
(0, 0) -> (0, 1) 과 (0, 1) -> (0, 0) 으로 움직인건 같은 걸로 봐야하므로
- (0, 0) -> (0, 1)을 저장할 때 (0, 1) -> (0, 0)도 함께 저장한다.
- 단, 배열로 저장할 시 참조값으로 비교하기 때문에 문자열로 바꾸어 Set에 저장한다.
[[0, 0], [0, 1]] 이 아니라 0001 로 저장
- 모든 방향을 실제 이동한 방향과 반대로 이동한 방향 두번 저장했으므로 length / 2 를 해서 반환해준다.
