반응형
밑의 링크는 프로그래머스에서의 문제 링크입니다.
코딩테스트 연습 - 방문 길이
programmers.co.kr
생각한 풀이 과정
- 캐릭터가 처음 걸어본 길의 정보를 저장할 set 변수를 하나 만들어줍니다.
- set 변수로 만드는 이유는 처음 걸어본 길만 저장해야하기 때문에 중복을 없애기 위해서입니다.
- 매개변수로 주어진 명령어에서 한 명령어씩 반복해봅니다.
- 명령어에 의해 어떤 한 점에서 다른 한 점으로 캐릭터가 이동할 때, 출발하는 점의 정보를 (출발점 x좌표, 출발점 y좌표, 명령어) 형식의 튜플로 만들어줍니다.
- 처음 걸어본 길의 길이를 구해야하기 때문에 1번 과정에서의 출발점에서 다음 점으로 이동하는 정보의 반대 정보도 튜플 형식으로 생각합니다. 왜냐하면, 예를 들어, (0, 0)에서 L 명령어를 통해 (-1, 0)으로 이동하는 길은 (-1, 0)에서 R 명령어를 통해 (0, 0)으로 이동하는 길과 같기 때문입니다.
- 4번 과정에서 생각한 (다음 점 x좌표, 다음 점 y좌표, 반대 방향의 명령어) 형식의 튜플을 만들어줍니다.
- 4번 과정에서 만든 점의 정보 튜플과 6번 과정에서 만든 점의 정보 튜플을 캐릭터가 처음 걸어본 길의 정보를 저장하는 set 변수에 넣어줍니다.
- 명령어에 의해 한 번 이동할 때 set 변수에 길의 정보를 2개 넣어주므로 실제로 캐릭터가 걸어간 길의 길이는 set 변수 길이의 절반입니다.
주의해야 할 점
어떤 한 점에서 다음 점으로 이동할 때, 그 이동한 길은 반대로 이동하는 경우의 수도 생각해야 합니다.
예를 들어, (0, 0)에서 명령어 U를 통해 (0, 1)로 이동한다면,
반대로 (0, 1)에서 명령어 D를 통해 (0, 0)으로 이동하는 경우도 고려해야 한다는 뜻입니다.
그래서 (0, 0)에서 명령어 U를 통해 (1, 0)으로 이동한 길은 처음에 지나온 길이라면 총 길이에 더해야 되지만,
곧바로 (1, 0)에서 명령어 D를 통해 (0, 0)으로 다시 원위치로 온다면 이미 그 길은 걸어본 길이기 때문에
총 길이에 더하면 안 됩니다.
좌표계가 -5 ≤ x ≤ 5, -5 ≤ y ≤ 5인 것도 유의해서 풀어야 합니다.
제출한 파이썬 코드
# 명령어 dir이 매개변수로 주어집니다.
def solution(dirs):
# 캐릭터가 처음 걸어본 길들의 정보들을 저장할 set 변수를 선언합니다.
first_load = set()
# 현재 캐릭터의 위치를 저장하는 리스트 변수를 선언합니다.
# 처음에는 0, 0에서 시작합니다.
point = [0, 0]
# 명령어에서 한 글자씩 반복해봅니다.
for dir in dirs:
# 현재 캐릭터가 있는 위치와 현재 명령어 글자를 저장할 변수를 선언합니다.
point_dir = None
# point_dir과 반대 방향의 정보를 저장할 변수를 선언합니다.
reverse_point_dir = None
# 명령어의 현재 글자가 U이고, 캐릭터의 y좌표에 1을 더했을 때 5보다 작거나 같다면
if dir == 'U' and point[1] + 1 <= 5:
# (현재 위치 x좌표, 현재 위치 y좌표, 현재 명령어 글자) 튜플을 point_dir에 저장합니다.
point_dir = (point[0], point[1], dir)
# 위로 이동하므로 현재 위치의 y좌표에 1을 더합니다.
point[1] += 1
# (다음 위치 x좌표, 다음 위치 y좌표, 현재 명령어 글자의 반대 방향) 튜플을 reverse_point_dir에 저장합니다.
reverse_point_dir = (point[0], point[1], 'D')
# 명령어의 현재 글자가 D이고, 캐릭터의 y좌표에 1을 뺐을 때 -5보다 크거나 같다면
elif dir == 'D' and point[1] - 1 >= -5:
# (현재 위치 x좌표, 현재 위치 y좌표, 현재 명령어 글자) 튜플을 point_dir에 저장합니다.
point_dir = (point[0], point[1], dir)
# 아래로 이동하므로 현재 위치의 y좌표에 1을 뺍니다.
point[1] -= 1
# (다음 위치 x좌표, 다음 위치 y좌표, 현재 명령어 글자의 반대 방향) 튜플을 reverse_point_dir에 저장합니다.
reverse_point_dir = (point[0], point[1], 'U')
# 명령어의 현재 글자가 R이고, 캐릭터의 x좌표에 1을 더했을 때 5보다 작거나 같다면
elif dir == 'R' and point[0] + 1 <= 5:
# (현재 위치 x좌표, 현재 위치 y좌표, 현재 명령어 글자) 튜플을 point_dir에 저장합니다.
point_dir = (point[0], point[1], dir)
# 오른쪽으로 이동하므로 현재 위치의 x좌표에 1을 더합니다.
point[0] += 1
# (다음 위치 x좌표, 다음 위치 y좌표, 현재 명령어 글자의 반대 방향) 튜플을 reverse_point_dir에 저장합니다.
reverse_point_dir = (point[0], point[1], 'L')
# 명령어의 현재 글자가 L이고, 캐릭터의 x좌표에 1을 뺐을 때 -5보다 크거나 같다면
elif dir == 'L' and point[0] - 1 >= -5:
# (현재 위치 x좌표, 현재 위치 y좌표, 현재 명령어 글자) 튜플을 point_dir에 저장합니다.
point_dir = (point[0], point[1], dir)
# 왼쪽으로 이동하므로 현재 위치의 x좌표에 1을 뺍니다.
point[0] -= 1
# (다음 위치 x좌표, 다음 위치 y좌표, 현재 명령어 글자의 반대 방향) 튜플을 reverse_point_dir에 저장합니다.
reverse_point_dir = (point[0], point[1], 'R')
# point_dir과 reverse_point_dir 튜플들을 first_load에 넣어줍니다.
first_load.add(point_dir)
first_load.add(reverse_point_dir)
# 캐릭터가 한 번 이동할 때 first_load에 길의 정보를 2번 넣어주므로
# 캐릭터가 처음 걸어본 길의 길이인 first_load의 길이의 절반을 반환합니다.
return len(first_load) // 2
제출 결과
※ 궁금한 부분, 이상한 점 및 오타는 댓글에 부탁드립니다.
※ 더 효율적이고 빠른 정답을 환영합니다.
반응형
댓글