문제
방문 길이 (https://programmers.co.kr/learn/courses/30/lessons/49994)
풀이
1. 문제 조건 해석
- 문제도 직관적이고, 변수 조건도 무난, 아주 심플하다.
2. 알고리즘
- U, L, D, R 을 하나씩 입력받으며, 그냥 순차적으로 트래킹하면 된다.
visited
를set
자료구조로 두어, 이미 지나간 길인지 아닌지 체크하면 된다.- 주의해야할 점은, 트래킹에는 '단방향성' 이 존재하지만, 길 자체는 '양방향' 이라는 점이다.
3. 코드
def solution(dirs):
dxs, dys = [-1, 0, 1, 0], [0, -1, 0, 1]
d = {"U": 0, "L":1, "D":2, "R": 3}
visited = set()
answer = 0
x, y = 0, 0
for dir in dirs:
i = d[dir]
nx, ny = x + dxs[i], y + dys[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
'취업과 기본기 튼튼 > 코딩 테스트 노트' 카테고리의 다른 글
[프로그래머스] 가장 먼 노드 (0) | 2019.09.21 |
---|---|
[프로그래머스] 야근 지수 (0) | 2019.09.21 |
[프로그래머스] 가장 큰 수 (7) | 2019.07.12 |
[BOJ] 5430. AC (2) | 2019.04.22 |
[BOJ] 2493. 탑 (2) | 2019.04.18 |