Jehyun Jung

Slowly Developing Myself

[Programmers] P150365 표 병합

Question

Language: Python

해당 문제의 핵심은 사전 순으로 가장 빠른 경로를 찾는다는 점에서 경로의 형태가 포맷팅되어 있는 점을 찾는 것이 핵심이다.

문제에서 보면 방향에 따라 서로 다른 문자가 경로에 추가되는데, 이때 사전 순으로 가장 빠른 경로를 구하기 위해서는 d -> l -> u -> r 형태로 이루어진 문자열이 사전순으로 가장 빠른 문자열이 될것이다.

위의 문자열의 순서를 고려하였을 때 가장 빠른 경로가 되는 경우는 아래와 같다.

d…l…rl…r…u 와 같이 이루어진 문자열의 형태이다. 가장 빠른 문자 순으로 먼저 배치하는 것이 관건이다.

  1. 우선 (x,y) -> (r,c)로 가기 위한 d,ㅣ,u,r의 갯수를 분석한다.
if x<r:
    directions["d"] +=(r-x)
else:
    directions["u"] +=(x-r)
    
if y<c:
    directions["r"] +=(c-y)
else:
    directions["l"] +=(y-c)
  1. d 방향을 고려한다.

우선, x에서 r로 이동하기 위해 필요한 d의 갯수를 고려한다. 그런 다음, 해당 위치에서 추가적으로 갈 수 있는 d 방향의 갯수를 계산한다. k//2는 남은 k갯수(왕복 고려)값과 비교해서 충분히 이동 가능하면 맨 아래쪽까지 이동한다. 이때, 추가적으로 이동하는 d의 갯수 만큼 나중에 u 방향으로 이동해줘야하기 때문에 그 값만큼을 추가해준다.

#x -> r로 이동하기 위한 d 갯수
answer+="d"*directions["d"]
#맨 아래쪽까지 도달가능한 경우, 해당 값만큼 추가적으로 d 방향으로 이동한다. 
additional_d=min(k//2, n-(x+directions["d"]))
#추가된 d의 갯수
answer+="d"*additional_d
#추가된 d에 따른 u의 갯수 추가
directions["u"]+=additional_d
k-=2*additional_d
  1. l 방향을 고려한다

d와 마찬가지로, 목적지의 열 좌표까지의 이동을 고려한다음 추가적으로 이동가능한 l 갯수를 계산한다.

answer+="l"*directions["l"]
additional_l=min(k//2, y-directions["l"]-1)
answer+="l"*additional_l
directions["r"]+=additional_l
k-=2*additional_l
  1. 남은 횟수동안 rl을 반복해서 이동한다.

위와 같이 이동을 하더라도 남은 횟수가 있다면, rl을 계속해서 반복하도록 한다.

answer+="rl"*(k//2)
  1. 이후, 앞서 추가된 d,l 만큼 u,r을 뒤에 추가해주도록 한다.
#r 이동
answer+="r"*directions["r"]
#u 이동
answer+="u"*directions["u"]

Solution

def solution(n, m, x, y, r, c, k):
    answer = ''
    
    dist=abs(x-r)+abs(y-c)
    
    #최단 거리외에 추가적으로 이동해야하는 거리
    k-=dist
    
    #남은 거리가 없거나, 남은 거리가 짝수가 아닌경우(왕복운동이 필요하므로) 불가능
    if k < 0 or k %2!=0:
        return "impossible"
    
    directions={"d":0,"l":0,"u":0,"r":0}
    
    if x<r:
        directions["d"] +=(r-x)
    else:
        directions["u"] +=(x-r)
        
    if y<c:
        directions["r"] +=(c-y)
    else:
        directions["l"] +=(y-c)

    #d 이동
    answer+="d"*directions["d"]
    additional_d=min(k//2, n-(x+directions["d"]))
    answer+="d"*additional_d
    directions["u"]+=additional_d
    k-=2*additional_d

    #l 이동
    answer+="l"*directions["l"]
    additional_l=min(k//2, y-directions["l"]-1)
    answer+="l"*additional_l
    directions["r"]+=additional_l
    k-=2*additional_l
    
    #rl 반복 이동
    answer+="rl"*(k//2)
    
    #r 이동
    answer+="r"*directions["r"]
    
    #u 이동
    answer+="u"*directions["u"]
    
    return answer

댓글남기기

참고