[프로그래머스] 방문 길이 [Summer/Winter Coding(~2018), 파이썬, 집합]

programmers.co.kr/learn/courses/30/lessons/49994

코딩테스트 연습 - 방문 길이

게임 캐릭터를 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 이하의 자연수입니다.

입출력 예

"ULURRDLLU"	7
"LULLLLLLU"	7

dirs answer

입출력 예 설명

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

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

풀이

먼저 dirs를 순회하며 방향에 따라 이동하는 코드를 작성해봅시다.

x = 0; y = 0
for d in dirs:
  if d == 'U':
    y += 1

  elif d == 'D':
    y -= 1

  elif d == 'R':
    x += 1

  elif d == 'L':
    x -= 1

우리는 0,0 좌표에서 시작하며, (-5, -5) ~ (5, 5) 위에서만 움직일 수 있습니다. 이를 반영하여 코드를 발전시켜 봅시다.

x = 0; y = 0
for d in dirs:
  if d == 'U' and y < 5:
    y += 1

  elif d == 'D' and y > -5:
    y -= 1

  elif d == 'R' and x < 5:
    x += 1

  elif d == 'L' and x > -5:
    x -= 1

이제 캐릭터가 이동하는 길이 처음 걸어본 길인지, 이미 방문한 길인지 확인하여 answer를 증가시켜주면 문제가 해결됩니다. 이때 (0, 0) -> (1, 1)과, (1, 1) -> (0, 0)을 같은 길로 취급해야 하는 점에 주의합니다.

visit을 (좌표1, 좌표2)의 집합으로 설정하고, 이동할 때마다 좌표를 visit에 더한 뒤 visit의 길이를 통해 처음 걸어본 이동 거리를 획득할 수 있습니다. 이는 집합이 중복을 허용하지 않기 때문입니다. 집합에 이미 존재하는 좌표를 더해도 집합의 길이는 늘어나지 않습니다. 다만, 이 경우 좌표1=(x1, y1) < 좌표2=(x2, y2)가 보장되어야 합니다. * 집합은 ((0, 0), (1, 1))과 ((1, 1), (0, 0))을 다른 요소로 취급합니다.

def solution(dirs):
    visit = set()
    x = 0; y = 0
    for d in dirs:
        if d == 'U' and y < 5:
            visit.add(((x, y), (x, y+1)))
            y += 1
            
        elif d == 'D' and y > -5:
            visit.add(((x, y-1), (x, y)))
            y -= 1
            
        elif d == 'R' and x < 5:
            visit.add(((x, y), (x+1, y)))
            x += 1
            
        elif d == 'L' and x > -5:
            visit.add(((x-1, y), (x, y)))
            x -= 1
    return len(visit)