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

Summer/Winter Coding(~2018 문제입니다)

---

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U: 위쪽으로 한 칸 가기
• D: 아래쪽으로 한 칸 가기
• R: 오른쪽으로 한 칸 가기
• L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

예를 들어, "ULURRDLLU"로 명령했다면

• 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.

• 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)

단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

예를 들어, "LULLLLLLU"로 명령했다면

• 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.

이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

제한사항

• dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
• dirs의 길이는 500 이하의 자연수입니다.

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
문제의 예시와 같습니다.

 

---

나의 풀이

def solution(dirs):
    history = set()
    d = {'U':0, 'D': 1, 'R': 2, 'L': 3} # U D R L 을 인덱스로 변경
    dx = [0, 0, 1, -1] # U D R L 순으로 x에 더해질 값
    dy = [1, -1, 0, 0] # U D R L 순으로 y에 더해질 값
    x, y = 0, 0 # 현재 캐릭터 좌표
    for move in dirs:
        tx, ty = x+dx[d[move]], y+dy[d[move]] # 이동 이후 임시 좌표
        if abs(tx) <= 5 and abs(ty) <= 5: # -5 ~ 5 사이에 있을 때만 이동
            # 방문한 경로를 표시하기 위해 출발지와 목적지를 set에 입력하지만 
            # a->b와 b->a를 같게 처리하기 위해 min, max로 순서를 지정
            history.add((min(x, tx), min(y, ty), max(x, tx), max(y, ty)))
            x, y = tx, ty # 실제 이동
    return len(history)

아이디어는 다음과 같다

• U D R L로 입력되는 것을 인덱스로 변경해주기 위해 Dict를 사용
• U D R L 중 하나가 입력되었을 때 x와 y에 얼만큼 더해줄 지 dx와 dy에 미리 저장해놓았다.
  • 예를 들어 D가 들어왔다면 d에 의해 'D'가 1로 변환되고, x는 dx[1]인 0 만큼,  y는 dy[1]인 -1 만큼 더해진다. 즉 y가 1 줄어드는 방향으로 이동하는 것이다.
• 일단 무조건 이동을 시킨 후 tx, ty에 임시 위치를 저장한다.
• tx와 ty가 -5~5를 벗어났다면 아무 작업도 하지 않는다.
• tx와 ty가 -5~5 범위 내에 있다면 set인 history에 추가한다.
  • 이때 a -> b로 이동한 것과 b -> a로 이동한 것은 set에서는 당연히 다른 값으로 판단하는데 문제에서 a->b나 b->a나 둘 다 같은 경로를 이동한 것이기 때문에 a->b와 b->a 모두 동일한 값이 history에 저장되어야 한다.
  • 그래서 min과 max를 사용해 무조건 작은 값 먼저 입력하도록 했다.
  • 여기서 주의할 점은 set에 add를 할 때 하나의 값만 들어갈 수 있으므로 전체를 괄호로 감싸 튜플의 형태로 넣어야 한다.
• history는 set이기 때문에 중복된 결과가 이미 제거되어 있다. 그렇기에 history의 길이를 구하면 한 번 이상 지나간 경로의 개수를 구할 수 있다.

 

테스트 결과