본문 바로가기

취업과 기본기 튼튼/코딩 테스트 노트

[프로그래머스] 방문 길이

문제

방문 길이 (https://programmers.co.kr/learn/courses/30/lessons/49994)

풀이

1. 문제 조건 해석

  • 문제도 직관적이고, 변수 조건도 무난, 아주 심플하다.

2. 알고리즘

  • U, L, D, R 을 하나씩 입력받으며, 그냥 순차적으로 트래킹하면 된다.
  • visitedset 자료구조로 두어, 이미 지나간 길인지 아닌지 체크하면 된다.
  • 주의해야할 점은, 트래킹에는 '단방향성' 이 존재하지만, 길 자체는 '양방향' 이라는 점이다.

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