2019년 상반기 LINE 인턴채용 코딩테스트 문제풀이

https://engineering.linecorp.com/ko/blog/2019-firsthalf-line-internship-recruit-coding-test/?fbclid=IwAR2kSQ5dlwDuwY8DQ3WPNh4Ho3XXcJjAyBLrt7CHF5fmtGsb9TUM5kNa93U 

2019년 상반기 LINE 인턴 채용 코딩테스트 문제 해설

 

코니의 위치 변화는 1초 후 1만큼, 매초마다 이전 이동거리 +1만큼 움직임

즉, += time
코니의 위치가 20만을 넘으면 따라잡지 못하는 것으로 간주.

브라운의 위치 변화는
매 초마다 b - 1, b + 1, 2 * b 중 랜덤하게 이동하므로 BFS 사용해 모든 경우의 수를 나열

큐를 이용하여, 모든 +1, -1, *2 에 대한 값을 c와 비교한 후, 같지 않다면 큐에 다시 집어넣는 형식.

 

※ 코딩테스트에서 큐를 사용할 때는 deque를 사용, 성능 차이가 많이난다!

코니와 브라운이 같은 시간에 같은 위치에 존재하면 catch
브라운의 값이 무작위적으로 바뀌므로 딕셔너리 활용

각 시간마다 브라운이 갈 수 있는 위치를 저장해 코니와 비교하여 시간과 위치가 같으면 정답

from collections import deque

c,b = map(int, input().split())


def catch_me(cony_loc, brown_loc):
    time = 0
    queue = deque()
    queue.append((brown_loc, 0)) # 위치와 시간 동시에 담는다
    visited = [{} for _ in range(200001)]
    # visited[위치][시간] 저장해서 브라운의 위치 시간 저장
    
    while cony_loc < 200000:
        cony_loc += time
        if time in visited[cony_loc]: # 코니와 브라운이 같은 시간에 같은 위치에 존재하면 catch
            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 new_position >= 0 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

            new_position = current_position + 1
            if new_position < 200001 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

            new_position = current_position * 2
            if new_position < 200001 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))

        time += 1

    


print(catch_me(c, b))

 

막상 풀어보니 deque를 이용해 같은 시간대에서 작업하므로 딕셔너리에 시간정보까지 담을 필요는 없어보이기도 한다.

 

from collections import deque

C, B = map(int, input().split())

time = 1
answer = 0
current_C = C
queue = deque([B])
found = False
while True:
    if current_C > 200000:
        answer = -1
        break
    current_C += time
    for _ in range(len(dq)):
        num = queue.popleft()
        b_plus = num + 1
        b_minus = num - 1
        b_times = num * 2

        if b_plus == current_C or b_minus == current_C or b_times == current_C:
            answer = time
            found = True
            break
        else:
            queue.append(b_plus)
            queue.append(b_minus)
            queue.append(b_times)

    if found:
        break
    time += 1
print(answer)