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

https://school.programmers.co.kr/learn/courses/30/lessons/49994#

프로그래머스

---

문제에서 원하는 바를 완벽히 이해하는 데 상당히 오래 걸렸다.

 

 - 캐릭터가 지나게 되는 선분을 count

 - 어떤 선분을 지난 적이 있으면 중복 카운트하지 않음

 - 선분에는 방향성이 없음

 

각 x, y 좌표가 0부터 10까지의 값을 가지는 11 * 11 크기의 이차원 배열을 만들고,

원점을 (5,5)로 놓고 시작했다.

캐릭터가 지나간 양 점을 배열에 저장해가며 체크해서 풀었다.

 

인풋으로 주어진 dirs 배열의 길이가 500이하로 꽤 작은 수여서 시간초과 걱정을 별로 안 하고 풀었지만,

배열이 길이가 길어진다면 그렇게 좋은 방법은 아닌 듯하다.

 

python

def solution(dirs):
    table = [[0 for i in range(11)] for j in range(11)]
    move = {'L':[0,-1], 'R':[0,1], 'U':[-1,0], 'D':[1,0]}
    
    # 원점 : 5,5
    x = 5
    y = 5
    
    # 캐릭터가 지나간 좌표 순서대로 구하기
    visited = [(5,5)] 
    for dir in dirs:
        nx, ny = x + move[dir][0], y + move[dir][1] # 이동좌표
        if 0 <= nx <= 10 and 0 <= ny <= 10: # 범위체크
            visited.append((nx,ny))
            x, y = nx, ny

    # 처음 걷는 길 count
    line = [(visited[i], visited[i+1]) for i in range(len(visited)-1)]
    answer = 0
    check = []
    for a,b in line:
        if (a,b) not in check and (b,a) not in check:
            answer += 1
            check.append((a,b))
    
    return answer

 

풀고 나서 생각해보니

그냥 처음부터 캐릭터가 지나게 되는 양 끝 점 좌표를 set에 집어넣고, set길이를 2로 나누어주면 되는 거였다.....!

 

수정한 코드

def solution(dirs):
    table = [[0 for i in range(11)] for j in range(11)]
    move = {'L':[0,-1], 'R':[0,1], 'U':[-1,0], 'D':[1,0]}
    
    # 원점 : 5,5
    x = 5
    y = 5
    
    visited = set() # 방문한 선분
    prev = (5,5)
    for dir in dirs:
        nx, ny = x + move[dir][0], y + move[dir][1] # 이동좌표
        if 0 <= nx <= 10 and 0 <= ny <= 10: # 범위체크
            visited.add((prev,(nx,ny)))
            visited.add(((nx,ny),prev))
            prev = (nx,ny)
            x, y = nx, ny
    return len(visited)//2