[TIL_Carrotww] 15 - 22/09/20

📝Carrotww의 코딩 기록장

🧲 알고리즘

🔍 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을 만족한다.
브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다

💡 풀이

from collections import deque

c = 11
b = 2


def catch_me(cony, brown):
    MAX = 200000
    time = 0
    queue = deque()
    queue.append((brown, 0))
    visited = [{} for _ in range(MAX + 1)]
    
    while cony <= MAX:
        cony += time
        if time in visited[cony]:
            return time
        for i in range(0, len(queue)):
            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

    return -1


print(catch_me(c, b))  # 5
print("정답 = 3 / 현재 풀이 값 = ", catch_me(10,3))
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51,50))
print("정답 = 28 / 현재 풀이 값 = ", catch_me(550,500))

🔍 간단 해설

• cony 의 위치는 시간이 지날 수록 빨라지니 수식을 써보면 cony += time 으로 걸어둔 후 visited 리스트 안에 BFS 방식으로 구한 brown 녀석의 거리가 index, 그 거리에서의 해당 시간이 dict()의 key 값으로 설정하여 구한 방식이다.
• 나름 간단해 보였지만 잘 풀리지 않았던 문제이다. 처음에는 시간별 위치를, 도착했던 위치를 따로 저장하려고 했으나 강의를 듣고 푼 방식이다.
• 코드 자체를 이해하고 보는데는 많이 빨라졌지만, bfs 계열이 머리속 생각이 코드로 쉽게 쓰여지지않아 좀 짜증났다 ㅠ

🧲 알고리즘

🔍 2020 kakao 문자열 압축 예전에 한 번 풀었던 문제이지만 듣는 알고리즘 강의에 나와 한 번 더 풀어본 문제이다.
오늘 머리가 잘 안돌아가서 엄청 오래걸렸다. 난 하루종일 알고리즘만 하는건 효율이 떨어지는 것 같다. 집중이 잘 안된다...

💡 풀이

🔍 이 문제는 내가 느끼기에 코딩에대한 기초가 얼마나 튼튼한지를 알 수 있는 문제인 것 같다.
python 기준으로 for문과 슬라이싱을 능수 능란하게 다룰 수 있다면 풀 수 있는 문제니 말이다.
난 문자열 다루는 문제가 재밌다.
기본적으로 문자열 다루는 문제는 복잡하지가 않다. 조금 과장해서 문제를 안 읽고 입출력 예제만 봐도 풀 수 있기 때문이다. 또한 나의 기본기가 얼마나 부족한지(?) 여실히 드러나기 때문이다.
설명은... 평소에 잘 적지도 않지만 이 문제는 더욱이 필요 없을 것 같다 ㅎㅎ
풀이만 적고 오늘 끝!

def string_compression(string):
    result = []
    if len(string) == 1:
        return 1
    
    for word_len in range(1, len(string) // 2 + 1):
        temp = ''
        word_temp = [string[x:x + word_len] for x in range(0, len(string), word_len)]
        cnt = 1
        for i in range(1, len(word_temp)):
            if word_temp[i - 1] == word_temp[i]:
                cnt += 1
            else:
                if cnt == 1:
                    temp += word_temp[i - 1]
                else:
                    temp += (str(cnt) + word_temp[i - 1])
                    cnt = 1
        if cnt > 1:
            temp += str(cnt) + word_temp[-1]
        else:
            temp += word_temp[-1]

        result.append(len(temp))

    return min(result)