알고리즘 실전 - 2019 상반기 LINE 인턴 채용 코딩테스트

나 잡아 봐라

❓

Q. 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오. 조건은 다음과 같다. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다. 코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다. 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다

c = 11 # 코니의 처음 위치
b = 2  # 브라운의 처음 위치
# 이렇게 입력된다면 
# 이 경우는 어떻게 늘어날지, 고민해보세요!

큐를 파이썬에서 사용하려면 기본 자료형 list()를 사용하면 된다고 튜터가 말해주었었다.

하지만 코딩테스트에서 큐를 사용할 때는 collections.deque를 사용하는 것이 좋다.

성능 차이가 있기 때문이다.

(스택은 그대로 list를 사용해도 됨)

# 코드 스니펫
from collections import deque

c = 11
b = 2


def catch_me(cony_loc, brown_loc):
    # 구현해보세요!
    return


print(catch_me(c, b))  # 5가 나와야 합니다!

문제의 조건

1. 코니의 위치 변화
   • 코니는 처음 위치에서 1초 후 1만큼, 매초마다 이전 이동거리 +1만큼 움직임. 즉 증가하는 속도가 1초마다 1씩
   • 속도: 1 2 3 4 5 6 7 8 9
   • 위치: 3 4 6 9 13 18 ...

2. 브라운의 위치 변화
   • B-1, B+1, 2*B에서 선택 가능
   • 시작: 2 가정
   • 1-1: 2 - 1 = 1
   • 1-2: 2 + 1 = 3
   • 1-3: 2 * 2 = 4
     • 1-1-1. 1 - 1 = 0
     • 1-1-2. 1 + 1 = 2
     • 1-1-3. 1 * 2 = 2
     • 1-2-1. 3 - 1 = 2
     • 1-2-2. 3 + 1 = 4
     • 1-2-3. 3 * 2 = 6
   • 이런식으로 무수한 갈래로 선택지가 나눠질 수 있음
   • 브라운의 모든 경우의 수를 비교하면서 몇 초에 언제 도착할 수 있는지 알아야 함

   💡

   너무 경우의 수가 많고 쉽게 일반화할 수 없다고 판단된다면 모든 경우의 수 를 다 나열해야함. 즉 BFS가 필요함.

3. 잡았다 라는 의미는 똑같은 시간에 똑같은 위치에 존재해야 함.
   • 시간은 1초마다 흘러감 + 1
   • 위치는 코니도 브라운도 값이 자유자재로 바뀜

   💡

   규칙적으로 변화하는 값은 배열 자유자재로 변화하는 값은 딕셔너리

   • 각 시간마다 브라운이 갈 수 있는 위치를 저장해야 한다.
   • 즉 [{}] 으로 배열 안에 딕셔너리를 넣는 방식

# 정답
from collections import deque

c = 11
b = 2


def catch_me(cony_loc, brown_loc):
    time = 0
    queue = deque()
    queue.append((brown_loc, 0)) # 브라운의 위치와 시간을 동시에 잡아주기 위함
    # 위치와 시간이 동시에 일치해야하지만 만났다고 할 수 있기에.
    visited = [{} for _ in range(200001)]
    # visited의 각 원소들은 각 시간 0초에 어느 곳을 갔는지 저장하기 위한 시간
    # visited[0] = { 2: True }, visited[1] = { 1:True, 3:True, 4:True} ...
    # 20만개의 딕셔너리를 배열에 넣음 [{}, {}, {}, ...]
    # visited[위치][시간]
    # visited[3] 에 5라는 키가 있냐? -> 3위치에 5초에 간적이 있나

    # 초기 위치는 2고 0초 이므로
    # 시간 0 1 -> visited[2] = { 0 : True }
    # 위치 2 1 -> visited[1] = { 1: True}
    #       3 -> visited[3] = { 1: True}
    #       4 -> visited[4] = { 1: True}

    # 시간이 2초일때 가능한 것은 다시
    # 시간 2 -> visited[2] = { 0 : True, 2: True }
    # 위치 0 -> visited[1] = { 1: True}
    #     2 -> visited[3] = { 1: True, 2: True}
    #     3 -> visited[4] = { 1: True, 2: True}
    #     4 -> visited[5] = { 2: True}
    #     5 -> visited[5] = { 6: True}
    #     6 -> visited[5] = { 8: True}
    #     8

    while cony_loc <= 200000:
        cony_loc += time #시간만큼 더해짐
        if time in visited[cony_loc]:
            return time
            # 이렇게 해준다면 이 시간대에 방문하게 된 것이므로 코니와 브라운이 만나게 된 시점을 알 수 있음

        for i in range(0, len(queue)):
            current_position, current_time = queue.popleft()
            new_time = current_time + 1

            new_position = current_position - 1
            if 0 <= new_position <= 20000:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

            new_position = current_position + 1
            if 0 <= new_position <= 20000:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

            new_position = current_position * 2
            if 0 <= new_position <= 20000:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))
            # 모든 경우의 수 저장을 위한 각각 격우의 수 저장
        time += 1
    return -1


print(catch_me(c, b))  # 5가 나와야 합니다!