Sparta_algorithm_course_05) velog

1. 강의 자료

 

https://www.notion.so/5-f51f57c84aef4626b580a5937adabca9#c90e4432a49b4737bc5aaa1a8c0e4dc4

[스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 5주차

---

2. 강의 듣기 전 계획과 생각

 

 

5주차 커리큘럼에는 실제로 출제되는 문제풀이를 위주로 강의가 담겨있었습니다. 프로그래머스에도 비슷한 문제들이 많이 올라와있는데, 난이도가 제법 있는 문제들인만큼 한번 강의를 듣기전에 혼자 풀어보기에 도전해보려고 합니다.

---

3. 문제풀이

 

▶ 2019년 상반기 LINE 인턴 채용 코딩테스트 - 나잡아봐라

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)):
            cur_pos, cur_time = queue.popleft()

            new_time = cur_time + 1
            new_brown_pos = cur_pos - 1
            # 조건 추가하지 않을 시 visited 의 일정 부분에서 무한루프가 발생
            if 0 <= new_brown_pos <= 200000 and new_time not in visited[new_brown_pos]:
                visited[new_brown_pos][new_time] = True
                queue.append((new_brown_pos, new_time))

            new_brown_pos = cur_pos + 1
            if 0 <= new_brown_pos <= 200000 and new_time not in visited[new_brown_pos]:
                visited[new_brown_pos][new_time] = True
                queue.append((new_brown_pos, new_time))

            new_brown_pos = cur_pos * 2
            if 0 <= new_brown_pos <= 200000 and new_time not in visited[new_brown_pos]:
                visited[new_brown_pos][new_time] = True
                queue.append((new_brown_pos, 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))

Comment : BFS에 대해서 탄탄히 다질 수 있었던 문제입니다. 그리고 항상 예외처리를 신경써야 한다는 것도 다시한번 되새길 수 있었습니다.

 

 

▶ 2020 카카오 신입 개발자 블라인드 채용 1차 코딩테스트 - 문자열 압축

input = "abcabcdede"


def string_compression(string):
    str_cut_num = 1
    result = []

    while str_cut_num <= len(string):
        str_temp = ""
        cnt = 1
        str_to_list = [string[i:i + str_cut_num] for i in range(0, len(string), str_cut_num)]
        # print(str_to_list)
        for idx in range(len(str_to_list) - 1):
            # if str_cut_num == 2:
            #     print(str_temp)
            if str_to_list[idx] == str_to_list[idx+1]:
                cnt += 1
            else:
                if cnt > 1:
                    str_temp += str(cnt)
                str_temp += str_to_list[idx]
                cnt = 1

        if cnt > 1:
            str_temp += str(cnt)
        str_temp += str_to_list[-1]

        result.append(len(str_temp))
        str_cut_num += 1

    return min(result)


print(string_compression(input))  # 14 가 출력되어야 합니다!

print("정답 = 3 / 현재 풀이 값 = ", string_compression("JAAA"))
print("정답 = 9 / 현재 풀이 값 = ", string_compression("AZAAAZDWAAA"))
print("정답 = 12 / 현재 풀이 값 = ", string_compression('BBAABAAADABBBD'))

Comment : 중간중간에 충분히 복잡도를 줄일 수 있는 흔적이 보입니다. 조금 더 보강하면 더 좋은 코드가 될것 같습니다.

 

 

▶ 2020 카카오 신입 개발자 블라인드 채용 1차 코딩테스트 - 올바른 괄호 문자열 만들기

from collections import deque

balanced_parentheses_string = "()))((()"


def is_correct_parentheses(string):  # 올바른 괄호인지 확인
    stack = []
    for s in string:
        if s == '(':
            stack.append(s)
        elif stack:
            stack.pop()
    return len(stack) == 0


def separate_to_u_v(string):  # u, v로 분리
    queue = deque(string)
    left, right = 0, 0
    u, v = "", ""

    while queue:  # 큐사용
        char = queue.popleft()
        u += char
        if char == '(':
            left += 1
        else:
            right += 1
        if left == right:  # 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 합니다. 즉, 여기서 괄 쌍이 더 생기면 안됩니다.
            break

    v = ''.join(list(queue))
    return u, v


def reverse_parentheses(string):  # 뒤집기
    reversed_string = ""
    for char in string:
        if char == '(':
            reversed_string += ")"
        else:
            reversed_string += "("
    return reversed_string


def change_to_correct_parentheses(string):
    if string == '':  # 1번
        return ''
    u, v = separate_to_u_v(string)  # 2번
    if is_correct_parentheses(u):  # 3번
        return u + change_to_correct_parentheses(v)
    else:  # 4번
        return '(' + change_to_correct_parentheses(v) + ')' + reverse_parentheses(u[1:-1])


def get_correct_parentheses(balanced_parentheses_string):
    if is_correct_parentheses(balanced_parentheses_string):
        return balanced_parentheses_string
    else:
        return change_to_correct_parentheses(balanced_parentheses_string)


print(get_correct_parentheses(balanced_parentheses_string))  # "()(())()"가 반환 되어야 합니다!

print("정답 = (((()))) / 현재 풀이 값 = ", get_correct_parentheses(")()()()("))
print("정답 = ()()( / 현재 풀이 값 = ", get_correct_parentheses("))()("))
print("정답 = ((((()())))) / 현재 풀이 값 = ", get_correct_parentheses(')()()()(())('))

Comment : 조건이 많다고해서 쫄지말고 차근차근 문제에 접근해야 한다는 것을 다시한번 되새길 수 있었습니다.

 

 

▶ 삼성 역량 테스트 - 새로운 게임

k = 4  # 말의 개수

chess_map = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]
start_horse_location_and_directions = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 2, 0],
    [2, 2, 2]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!
# 동 서 북 남
# →, ←, ↑, ↓
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]


def get_new_d(d):
    if d % 2 == 0:
        return d + 1
    else:
        return d - 1


def get_game_over_turn_count(horse_count, game_map, horse_location_and_directions):
    n = len(game_map)
    turn_cnt = 1
    visited = [[[] for _ in range(n)] for _ in range(n)]

    for i in range(horse_count):
        r, c, d = horse_location_and_directions[i]
        visited[r][c].append(i)

    while turn_cnt <= 1000:
        for horse_idx in range(horse_count):
            r, c, d = horse_location_and_directions[horse_idx]
            new_r = r + dr[d]
            new_c = c + dc[d]

            if not 0 <= new_r < n or not 0 <= new_c < n or game_map[new_r][new_c] == 2:
                new_d = get_new_d(d)

                horse_location_and_directions[horse_idx][2] = new_d
                new_r = r + dr[new_d]
                new_c = c + dc[new_d]

                if not 0 <= new_r < n or not 0 <= new_c < n or game_map[new_r][new_c] == 2:
                    continue

            moving_arr = []
            for i in range(len(visited[r][c])):
                visit_idx = visited[r][c][i]
                if horse_idx == visit_idx:
                    moving_arr = visited[r][c][i:]
                    visited[r][c] = visited[r][c][:i]
                    break

            if game_map[new_r][new_c] == 1:
                moving_arr = reversed(moving_arr)

            for idx in moving_arr:
                visited[new_r][new_c].append(idx)
                horse_location_and_directions[idx][0], horse_location_and_directions[idx][1] = new_r, new_c

            if len(visited[new_r][new_c]) >= 4:
                return turn_cnt

        turn_cnt += 1

    return -1


print(get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))  # 2가 반환 되어야합니다

start_horse_location_and_directions = [
    [0, 1, 0],
    [1, 1, 0],
    [0, 2, 0],
    [2, 2, 2]
]
print("정답 = 9 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))

start_horse_location_and_directions = [
    [0, 1, 0],
    [0, 1, 1],
    [0, 1, 0],
    [2, 1, 2]
]
print("정답 = 3 / 현재 풀이 값 = ", get_game_over_turn_count(k, chess_map, start_horse_location_and_directions))

Comment : 복잡한 기능들이 반복되게 되면 함수로 빼서 적용하는 것이 코드의 성능 단순화에 도움이 된다는 것을 알 수 있었던 문제입니다.

 

 

▶ 삼성 역량 테스트 - 구슬 탈출

from collections import deque

game_map = [
    ["#", "#", "#", "#", "#"],
    ["#", ".", ".", "B", "#"],
    ["#", ".", "#", ".", "#"],
    ["#", "R", "O", ".", "#"],
    ["#", "#", "#", "#", "#"],
]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def move_until_wall_or_hole(x, y, bump_x, bump_y, game_map):
    move_cnt = 0
    while game_map[x + bump_x][y + bump_y] != "#" and game_map[x][y] != "O":
        x += bump_x
        y += bump_y
        move_cnt += 1

    return x, y, move_cnt


def is_available_to_take_out_only_red_marble(game_map):
    n, m = len(game_map), len(game_map[0])
    visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
    queue = deque()
    red_row, red_col, blue_row, blue_col = -1, -1, -1, -1

    for x in range(n):
        for y in range(m):
            if game_map[x][y] == "R":
                red_row, red_col = x, y
            elif game_map[x][y] == "B":
                blue_row, blue_col = x, y

    visited[red_row][red_col][blue_row][blue_col] = True
    queue.append((red_row, red_col, blue_row, blue_col, 0))

    while queue:
        red_row, red_col, blue_row, blue_col, try_cnt = queue.popleft()

        if try_cnt > 10:
            break

        for i in range(4):
            next_red_row, next_red_col, red_cnt = move_until_wall_or_hole(red_row, red_col, dx[i], dy[i], game_map)
            next_blue_row, next_blue_col, blue_cnt = move_until_wall_or_hole(blue_row, blue_col, dx[i], dy[i], game_map)

            if game_map[next_blue_row][next_blue_col] == "O":
                continue
            if game_map[next_red_row][next_red_col] == "O":
                return True
            if next_red_row == next_blue_row and next_red_col == next_blue_col:
                if red_cnt > blue_cnt:
                    next_red_row -= dx[i]
                    next_red_col -= dy[i]
                else:
                    next_blue_row -= dx[i]
                    next_blue_col -= dy[i]

            if not visited[next_red_row][next_red_col][next_blue_row][next_blue_col]:
                visited[next_red_row][next_red_col][next_blue_row][next_blue_col] = True
                queue.append((next_red_row, next_red_col, next_blue_row, next_blue_col, try_cnt + 1))

    return False


print(is_available_to_take_out_only_red_marble(game_map))  # True 를 반환해야 합니다



game_map = [
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
    ["#", ".", "O", ".", ".", ".", ".", "R", "B", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = False / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))


game_map = [
["#", "#", "#", "#", "#", "#", "#"],
["#", ".", ".", "R", "#", "B", "#"],
["#", ".", "#", "#", "#", "#", "#"],
["#", ".", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", ".", "#"],
["#", "O", ".", ".", ".", ".", "#"],
["#", "#", "#", "#", "#", "#", "#"]
]
print("정답 = True / 현재 풀이 값 = ", is_available_to_take_out_only_red_marble(game_map))

Comment : 계속 문제해결이 안되었던 문제입니다. 결국 강의를 통해 해답을 알게 되었는데, 빨간 공과 파란 공이 겹쳤을 때의 경우를 고려하지 않았던 것이 문제였습니다. 전형적인 BFS 문제에서 조금 더 나아간 문제라 많은 도움이 되었습니다.

 

 

▶ 삼성 역량 테스트 - 치킨 배달

import sys
from itertools import combinations

n = 5
m = 3

city_map = [
    [0, 0, 1, 0, 0],
    [0, 0, 2, 0, 1],
    [0, 1, 2, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 2],
]


def get_min_city_chicken_distance(n, m, city_map):
    customer_loc = []
    chicken_loc = []

    for i in range(n):
        for j in range(n):
            if city_map[i][j] == 1:
                customer_loc.append([i+1, j+1])
            elif city_map[i][j] == 2:
                chicken_loc.append([i+1, j+1])

    chicken_number_of_case = list(combinations(chicken_loc, m))

    road_sum_number_of_case = []
    for case in chicken_number_of_case:
        road_sum = 0
        for customer_x, customer_y in customer_loc:
            chicken_road = sys.maxsize
            for loc_x, loc_y in case:
                chicken_road = min(chicken_road, abs(customer_x - loc_x) + abs(customer_y - loc_y))
            road_sum += chicken_road
        road_sum_number_of_case.append(road_sum)

    return min(road_sum_number_of_case)


# 출력
print(get_min_city_chicken_distance(n, m, city_map))  # 5 가 반환되어야 합니다!


city_map = [
    [1, 2, 0, 0, 0],
    [1, 2, 0, 0, 0],
    [1, 2, 0, 0, 0],
    [1, 2, 0, 0, 0],
    [1, 2, 0, 0, 0]
]
print("정답 = 11 / 현재 풀이 값 = ", get_min_city_chicken_distance(5,1,city_map))


city_map = [
    [0, 2, 0, 1, 0],
    [1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [2, 0, 0, 1, 1],
    [2, 2, 0, 1, 2]
]
print("정답 = 10 / 현재 풀이 값 = ", get_min_city_chicken_distance(5,2,city_map))

Comment : 여러 개 중에서 특정 개수를 뽑는 경우의 수. 즉, 여러 개 중에서 M 개를 고른 뒤, 가장 작게 되는 경우를 반환해야하는 경우에는, 모든 경우의 수를 다 봐야 한다는 팁을 얻을 수 있었습니다. 또한 이 두가지를 해결하기 위해서는 조합을 사용해야 한다는 것도 알 수 있었습니다.

 

 

---

 

4. 5주차 강의를 통해 새롭게 알게된 점

 

아직 부족하지만 강의를 들으면서 부쩍 성장한 느낌이 들었습니다. 하반기 코딩테스트에서 좋은 결과가 있을 것 같습니다.