2022.11.17 TIL

조원들과 알고리즘 공부
1. 양꼬치
2. 삼각형의 길이

쉽게 배우는 알고리즘 5주차
2019년 상반기 LINE 인턴 채용 코딩테스트

from collections import deque
c = 550
b = 510
def catch_me(cony_loc, brown_loc):
    sec = 0
    queue = deque()
    queue.append(brown_loc)
    temp_queue = deque()
    while cony_loc not in temp_queue:       # 여기서 1차로 1시간이 무조건 O(N)만큼 소모된다.
        print(len(temp_queue))
        sec += 1
        cony_loc += sec             # 시간에 비례해서 속도 빨라짐
        temp_queue = deque()
        if cony_loc > 200000:
            return "game over"
        for temp_brown_loc in queue:        # 시간 단계당 3배 씩 늘어서 28단계까지 가기 어려움 계산 불가
            if 0 <= (temp_brown_loc - 1) <= 200000 and (temp_brown_loc - 1) not in temp_queue:
                temp_queue.append(temp_brown_loc - 1)
            if 0 <= (temp_brown_loc + 1) <= 200000 and (temp_brown_loc + 1) not in temp_queue:
                temp_queue.append(temp_brown_loc + 1)
            if 0 <= (temp_brown_loc * 2) <= 200000 and (temp_brown_loc * 2) not in temp_queue:
                temp_queue.append(temp_brown_loc * 2)
        queue = temp_queue
    return sec
print(catch_me(c, b))  # 5가 나와야 합니다!       # 계산 방법은 문제가 없으나 12번째 라인에서 참, 거짓 판단에 시간이 많이 소모되는 것으로 보임
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51,50))

답안지

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)]
    while cony_loc < 200000:
        cony_loc += time
        if time in visited[cony_loc]:
            return time
        for i in range(0, len(queue)):  # Q. Queue 인데 while 을 안 쓰는 이유를 고민해보세요!
            current_position, current_time = queue.popleft()
            new_position = current_position - 1
            new_time = current_time + 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))
print("정답 = 3 / 현재 풀이 값 = ", catch_me(10,3))
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51,50))
print("정답 = 28 / 현재 풀이 값 = ", catch_me(550,500))

• 방향은 비슷했지만 cony의 위치와 brown의 위치를 비교하는 부분에서 시간 복잡도 차이가 컸던 것 같다. cony_loc = 550, brown_loc = 510을 입력했을 때 계산이 불가할 정도로 시간이 오래 걸린다. 비교는 for로 전체를 돌리는 것이 아닌 타겟하여 돌려야함을 배웠다.
• 역시 실전문제는 어렵다.