카카오 인턴십 코딩테스트 문제풀이 2번째 -> 2020년
문제 풀어보고 회고록 작성하기! 3.5문제 밖에 못 풀었지만 작성해 본다.

• 문제 : 5문제
• 제한 시간 : 4시간
• 합격 커트라인 : 3~3.5솔
• 나의 결과 : 3.5솔 (3시간도 안돼서 3.5솔을 찍었는데, 1.5문제를 1시간 손도 못댄게 참..)

2019년보다 오히려 쉬운 것 같았다. 아니면 2019년에 크게 맞아서 2020년 거는 적응을 좀 한 것일 수도...
항상 느끼는 거지만 이분 탐색 , DFS/BFS, 최단 경로 이 3가지 개념은 정확히 알고 들어가면 코테는 금방 풀 수 있을 것 같다.

1. 키패드 누르기

문제

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
5. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

아이폰 잠금화면 키패드를 주고, 오른손가락으로 누르는지 왼 손가락으로 누르는지 푸는 문제이다.
내 생각에는 문제는 굉장히 간단했지만 생각보다 오래 걸렸는데, 이유가

1. 문제를 꼼꼼히 읽어볼 것 ( 2,3번을 안 읽고 풀었었다.)
2. 키패드를 2중 리스트로 어떻게 나타낼 것인지

이 2가지 고민만 해결하면 쉽게 풀렸던 문제다. 원래는 10분컷을 해야할 수준인데 25분이나 걸렸다.

해결 방법은 다음 키패드와의 거리는 그냥 좌표 끼리 빼서 더하면 되는 것이고, 왼손과 오른손위치를 저장한 다음 왼손잡이인지 오른손잡이인지 2,5,8,0 인 경우에만 거리를 계산하고 판단하면 된다.

정답 코드

# 소요시간 : 25분
# Map을 1을 (1,1), 3은 (1,3), 9는 (3,3)으로 하자.

def distance(now, nex):
    y_dist = abs(now[0] - nex[0])
    x_dist = abs(now[1] - nex[1])
    return y_dist + x_dist


def solution(numbers, hand):
    left = [4, 1]  # (y,x)
    right = [4, 3]
    answer = ''
    for num in numbers:
        y = int(num / 3)
        x = num % 3
        if x == 0:
            x = 3
        else:
            y += 1

        if num == 0:
            y = 4
            x = 2
        nex = [y, x]
        print(nex)

        if num == 1 or num == 4 or num == 7:
            left = nex
            answer += 'L'
        elif num == 3 or num == 6 or num == 9:
            right = nex
            answer += 'R'
        else:
            left_dist = distance(left, nex)
            right_dist = distance(right, nex)
            print("left dist : ",left_dist)
            print("right dist : ",right_dist)
            if left_dist > right_dist:
                right = nex
                answer += 'R'
            elif right_dist > left_dist:
                left = nex
                answer += 'L'
            else:
                if hand == 'right':
                    right = nex
                    answer += 'R'
                else:
                    left = nex
                    answer += 'L'
        print("left : ", left)
        print("right : ", right)


    return answer

2. 수식 최대화

문제

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

프로그래머스에서 Level 2로 뜬 것 치곤 가장 어려웠다. 연산이 주어졌을 때 연산의 우선순위를 나의 마음대로 지정할 수 있고, 잘 지정해서 절댓값의 최댓값을 만드는 것이 문제였다.

나의 고민 과정은 이러했다.

1. 일단 문자열로 입력 받으니 연산자와 숫자로 구분을 하자
2. 근데, 연산자가 2가지 이상으로 입력 받을 때는 구분을 어떻게 할까?
3. 1가지만 받을 때는 값이 하나밖에 나오지 않으므로 예외로 바로 처리를 하는 것으로 하자.
4. 2가지인 경우는, 우선 순위의 경우를 내가 다 배열로 저장해 놓고 푸는 것으로 하자.
5. 연산을 하고 나서 결과값을 뒷 숫자에 저장하고, 연산이 다 끝나면 한번에 배열에서 다 없애버리자.

4번이 가장 찜찜했던게, 사실 자동화가 아닌 반 노가다로 푸는 것이라, 이렇게 푸는 것이 맞나..? 라고 생각이 든다. 내일 스터디원들과 풀이 과정을 공유하면서 한번 다른 측면으로 어떻게 생각을 했는지 들어보고 업데이트 해야겠다.

아마 딕셔너리 타입을 이용해서 풀어봤을 수도 있을 것 같다. 하지만 나는 이렇게 했고, 마지막에 지울때 remove 를 사용하면 값이 하나밖에 지워지지 않으므로 del 을 사용해서 인덱스를 이용해 지우는 것이 맞다. 이 부분에서 20분 정도 소모를 했다.

정답 코드

def solution(expression):
    calc_list = []
    num_list = []
    num = ''
    answer = 0
    for e in expression:
        if e == '+':
            calc_list.append(e)
            num_list.append(int(num))
            num = ''
        elif e == '-':
            calc_list.append(e)
            num_list.append(int(num))
            num = ''
        elif e == '*':
            calc_list.append(e)
            num_list.append(int(num))
            num = ''
        else:
            num += e

    calc = list(set(calc_list))  # 연산자 개수
    num_list.append(int(num))
    one_len = [0]
    two_len = [[0, 1], [1, 0]]
    three_len = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

    fact = []
    if len(calc) == 1:
        fact = one_len
    elif len(calc) == 2:
        fact = two_len
    else:
        fact = three_len

    if len(calc) == 1:
        idx = 0
        while idx < len(calc_list):
            if calc[0] == '-':
                num_list[idx + 1] = num_list[idx] - num_list[idx + 1]
            elif calc[0] == '+':
                num_list[idx + 1] = num_list[idx] + num_list[idx + 1]
            else:
                num_list[idx + 1] = num_list[idx] * num_list[idx + 1]
            idx += 1

        answer = max(abs(num_list[len(calc_list)]), answer)
    else:
        for f in fact:  # 연산자 경우 별로 따지는 곳
            cl = calc_list.copy()
            nl = num_list.copy()
            for op in f:  # 연산자 우선 순위 보이는 곳
                # 우선 순위에 따라서 탐색.
                idx = 0
                pop_list = []
                while idx < len(cl):
                    if cl[idx] == calc[op]:  # 우선 순위가 맞으면
                        if calc[op] == '-':
                            val = nl[idx] - nl[idx + 1]
                        elif calc[op] == '+':
                            val = nl[idx] + nl[idx + 1]
                        else:
                            val = nl[idx] * nl[idx + 1]
                        pop_list.append(idx)
                        nl[idx + 1] = val
                    idx += 1

                pop_list.sort()
                minus = 0
                for p in pop_list:
                    del nl[p - minus]
                    del cl[p - minus]
                    minus += 1

            answer = max(abs(nl[0]), answer)

    return answer

3.경주로 건설

• 걸린 시간 : 1시간

문제
건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.
제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.
설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.
경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.
경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.
이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다.
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.
예를 들어, 아래 그림은 직선 도로 6개와 코너 4개로 구성된 임의의 경주로 예시이며, 건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.
도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.

이렇게 글로 읽으면 이해가 안되지만, 문제 설명에 친절하게 그림까지 나와있다. 결론은 최단 경로 + 가격 문제이다.

dfs를 이용한 가지치기를 이용해 풀었는데, 어느 부분에서 코드를 잘못 짰는지 자꾸 무한 루프를 돌기 시작했다. 아마 지점의 방문여부를 계산하는 과정에서 무한루프를 돈 것 같다.

그래서 압박감을 느껴서 여러가지 해결 방안을 생각 못하고 급하게 해결을 해보았는데, 바로 dp를 이용해서 지점의 최저 가격을 기억해 놓는 것이었다.

이 코드를 추가하니까 바로 풀렸다.

내 코드의 프로세스는 그러니까

1. 처음엔 무조건 직진을 한다
2. 안 가본곳 중에 갈 수 있는 곳을 다 가본다. 이 때 방향을 매개변수로 전달을 해서, 방향이 바뀌면 무조건 코너가 생긴 것이다.(뒤로 가는 경우는 없으므로)
3. 이런식으로 종점에 도달하는 경우에 가격을 비교 한다.
4. 중간에 지점을 방문했는데 가격이 최소 가격이 아니면 다시 돌아간다.(DP)

이 문제를 풀면서 DP와 DFS/BFS를 정말 많이 숙달시켜야 겠구나 라는 생각이 들었다.

정답 코드

d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
# (y,x)
isvisited = [[0 for _ in range(26)] for _ in range(26)]  # 방문 여부
dp = [[987654321 for _ in range(26)] for _ in range(26)]
answer = 987654321


# 왜 자꾸 무한루프 돌지?

def solution(board):
    isvisited[0][0] = 1
    isvisited[0][1] = 1
    dfs(0, 1, 0, 100, board)
    isvisited[0][1] = 0
    isvisited[1][0] = 1
    dfs(1, 0, 1, 100, board)
    return answer

def dfs(y, x, pre_dir, value, board):
    if board[y][x] == 1:
        return

    # 이거 추가하니까 풀리넹?
    if dp[y][x] >= value:
        dp[y][x] = value
    else:
        return

    end = len(board) - 1
    global answer

    if y == end and x == end:
        answer = min(answer, value)
        print(answer)
        return

    for direct in range(4):
        ny = y + d[direct][0]
        nx = x + d[direct][1]
        if 0 <= ny < len(board) and len(board) > nx >= 0:  # 맵 안에 들어와 있을 때
            if isvisited[ny][nx] == 0 and board[ny][nx] == 0:
                isvisited[ny][nx] = 1
                if pre_dir == direct:  # 직진
                    dfs(ny, nx, direct, value + 100, board)
                else:  # 꺾는다
                    dfs(ny, nx, direct, value + 600, board)
                isvisited[ny][nx] = 0

4. 보석 쇼핑

• 0.5솔
• 걸린 시간 : 정확성은 15분

문제

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

간단하게 풀릴 줄 알았는데, 시간 초과가 도저히 풀리지를 않는다. 딕셔너리를 이용해서 시간을 엄청나게 줄였는데, 다른 알고리즘을 사용해야 할 듯 하다.
지금보니까 이분탐색을 이용하는게 맞는 것 같다. 이분 탐색을 이용하여 내일 다시 풀어봐야겠다.

"""
1트 : 정확성은 통과, 효율성은 통과 못함
효율성 통과 못할 줄 알았음..이거 완전 노가다로 푼거라
일단은 0.5솔, 소요시간 : 15분
"""

def solution(gems):
    jewelry = list(set(gems))
    answer = [0, 99999]
    if len(jewelry) == 1:
        answer = [1, 1]
    else:
        for idx in range(len(gems)):
            l = jewelry.copy()
            for j in range(idx, len(gems)):
                if gems[j] in l:
                    l.remove(gems[j])
                if len(l) == 0:
                    if answer[1] - answer[0] > j - idx:
                        answer = [idx+1, j+1]
                    break


    return answer

"""
2트 : 딕셔너리 타입을 사용해보니 확실히 시간이 많이 줄었다. 정확성 코드는 22ms가 제일 오래걸리는것일정도(1트때는 3300까지감)
근데 이것도 시간초과가 뜨네.. (테케 5,7,8,10,11,12,13,14,15)

결론은 sort 횟수를 줄여아 하는 것 같다.

"""

def solution(gems):
    jewelry = list(set(gems))  # 보석의 종류
    answer = [0, 99999]
    if len(jewelry) == 1:
        answer = [1, 1]
    else:
        dic = {}
        for idx in range(len(gems)):
            dic[gems[idx]] = idx

            if len(dic) == len(jewelry):
                # 길이가 일치하고, 제일 작았던 인덱스놈에게 변화가 있으면
                sorted_dic = sorted(dic.items(), key=lambda item: item[1])
                if sorted_dic[len(dic) - 1][1] - sorted_dic[0][1] < answer[1] - answer[0]:
                    answer = [sorted_dic[0][1] + 1, sorted_dic[len(dic) - 1][1] + 1]
                    dic.pop(sorted_dic[0][0])

    return answer

제일 어려운 문제는 손도 못대서, 추후에 열심히 풀어서 업데이트 할 예정이다.