Programmers / 방문 길이 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 방문 길이 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

 
문제 설명
 

---

 
나의 풀이
 

def solution(dirs):
    answer = 0
    dy = 5
    dx = 5
    visited = [[0] * 11 for _ in range(11)]

    visited[dy][dx] = 1

    for move in dirs:
        if move == "L":
            x = dx - 1
            y = dy
            if 0 < x < 10 and 0 < y < 10:
                visited[y][x] = 1
                dx = dx - 1
                dy = dy
        elif move == "R":
            x = dx + 1
            y = dy
            if 0 < x < 10 and 0 < y < 10:
                visited[y][x] = 1
                dx = dx + 1
                dy = dy
        elif move == "U":
            x = dx
            y = dy + 1
            if 0 < x < 10 and 0 < y < 10:
                visited[y][x] = 1
                dx = dx
                dy = dy + 1
        elif move == "D":
            x = dx
            y = dy - 1
            if 0 < x < 10 and 0 < y < 10:
                visited[y][x] = 1
                dx = dx
                dy = dy - 1

    for i in visited:
        for j in i:
            if j == 1:
                answer += 1

    return answer

 
처음에는 좌표평면이 작다는 사실을 가지고 작은 만큼 2차원 배열을 만들어서 이동한 거리는 1로 만들어서 푸는 법을 시도 했지만 문제점을 찾지 못하고 틀렸다.
 

def solution(dirs):
    answer = 0
    sets = set()
    y, x = 0, 0

    move = {"U": (1, 0), "D": (-1, 0), "L": (0, -1), "R": (0, 1)}

    for m in dirs:
        dy, dx = move[m]
        ny = y + dy
        nx = x + dx
        if -5 <= ny <= 5 and -5 <= nx <= 5:
            sets.add((ny, nx))
            y = ny
            x = nx

    answer = len(sets)

    return answer

 
두 번째 풀이도 첫 번째 풀이처럼 이동한 거리만 계산을 해서 풀려고 시도 했다가 틀렸다.
 
(답)

def solution(dirs):
    answer = 0
    sets = set()
    y, x = 0, 0

    move = {"U" : (1, 0), "D" : (-1, 0), "L" : (0, -1), "R" : (0, 1)}

    for m in dirs:
        dy, dx = move[m]
        ny = y + dy
        nx = x + dx
        if -5 <= ny <= 5 and -5 <= nx <= 5:
            sets.add(((y, x), (ny, nx))) # 기존 위치, 이동 위치
            sets.add(((ny, nx), (y, x))) # 이동 위치, 기존 위치
            y = ny
            x = nx

    answer = len(sets) // 2
    
    return answer

 
입출력 예 1를 보완하는 풀이 방법이다. 2번째 풀이와 다른 점이 있다면 이 풀이는 어디서 출발해서 어디로 도착했는지까지 넣어준다. 이걸 넣는 이유는 다음과 같다.
 
ex) "ULURRDLLU" 기준
 
처음 U을 하게 되면 y = 1, x = 0이다. 즉 (1, 0)이 들어가게 된다. 하지만 7번째 L에서 (1, 1)에서 (1, 0)으로 이동할 때 처음 U와 겹쳐서 캐릭터가 처음 걸어본 길이지만 좌표가 겹쳐서 누락되게 된다. 이걸 방지하기 위해서는 캐릭터가 어디서 이동해서 어디로 도착했는지까지 넣어줘야 한다.

---

※ 알아야 할 것

파이썬의 set은 중복을 허용하지 않고 순서가 없다는 특징을 가지고 있다. C++의 set에서 자동정렬을 해준다는 점을 빼면 유사한 자료형 특징을 가지고 있다.