CodeWars 17 : Directions Reduction

문제설명

Once upon a time, on a way through the old wild mountainous west,…
… a man was given directions to go from one point to another. The directions were "NORTH", "SOUTH", "WEST", "EAST". Clearly "NORTH" and "SOUTH" are opposite, "WEST" and "EAST" too.

Going to one direction and coming back the opposite direction right away is a needless effort. Since this is the wild west, with dreadfull weather and not much water, it's important to save yourself some energy, otherwise you might die of thirst!

How I crossed a mountainous desert the smart way.
The directions given to the man are, for example, the following (depending on the language):

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"].
or
{ "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" };
or
[North, South, South, East, West, North, West]

You can immediatly see that going "NORTH" and immediately "SOUTH" is not reasonable, better stay to the same place! So the task is to give to the man a simplified version of the plan. A better plan in this case is simply:

["WEST"]
or
{ "WEST" }
or
[West]

문제요약 : 'WEST' <-> 'EAST'처럼 서로 상충되는 방향이 나오면 방향 둘 다 지우고, 마지막에 남은 방향들만 return

제한사항

["NORTH", "EAST", "WEST", "SOUTH", "WEST", "WEST"]

위 예시 리스트에서 첫 번째 "NORTH"와 네 번째 "SOUTH"는 떨어져있지만 중간에 "EAST" "WEST"가 지워지면 서로 맞닿게 되므로 이 경우에도 지워져야 합니다. 그러므로 최종 return 은 ["WEST","WEST"]가 됩니다.

입출력 예시

dirReduc(["NORTH", "WEST", "SOUTH", "EAST"]) == ["NORTH", "WEST", "SOUTH", "EAST"]

풀이

def dirReduc(arr):
    # arr가 주어지지 않으면 바로 빈 리스트 리턴
    if not arr:
        return []
    # 상충되는 방향들 딕셔너리 패킹
    zero_sum_dir_dic = {
        'EAST': 'WEST',
        'WEST': 'EAST',
        'SOUTH': 'NORTH',
        'NORTH': 'SOUTH'
    }
    # 이전 요소의 방향을 저장할 포인터
    pointer = '' 
    # 최종 결과 저장용 list
    result = []
    for v in arr:
        # result 리스트에 삽입
        result.append(v)
        # 포인터에 저장된 이전 방향이 현재 방향과 상충된다면 슬라이싱으로 둘 다 잘라냄
        if pointer == zero_sum_dir_dic[v]:
            result = result[:-2]
            # 포인터 초기화
            pointer = ''
        else:
            # 상충되지 않는다면 포인터에 방향을 저장
            pointer = v
    # 모든과정을 끝냈는데 arr가 result랑 똑같다면 return 아니면 재귀로 함수호출
    return result if result == arr else dirReduc(result)

다른풀이

opposite = {'NORTH': 'SOUTH', 'EAST': 'WEST', 'SOUTH': 'NORTH', 'WEST': 'EAST'}

def dirReduc(plan):
    new_plan = []
    for d in plan:
        if new_plan and new_plan[-1] == opposite[d]:
            new_plan.pop()
        else:
            new_plan.append(d)
    return new_plan

스택을 활용해 더욱 간단하게 풀었습니다. 저도 처음에 생각한 방식인데, 제한사항에 담긴 예시처리가 안될거라 생각했는데 다시 생각해보니 예시처리도 가능하네요. ㅠ 오늘도 삽질을..