손가락놀이터

문제 리뷰

1. 작년 카카오 코테를 보면서 스스로 많이 부족하다는 것을 알았습니다... 그동안 혼자서 공부하면서 어느정도 실력이 늘었다고 생각을 했고 옛날에 못풀었던 문제를 다시 풀었습니다.
2. 최소비용을 찾는 문제인 것을 다익스트라를 활용해야겠다고 생각했습니다.
3. 같이 어디까지 가는지 고민하다가, 모든 노드를 같이 갔을 때 가장 최소인 비용을 찾으면 되겠다고 생각하고 찾았습니다.
4. 문제에 효율성도 있는 것으 봐서는 우선순위 큐를 활용한 다익스트라아니면 안될 것(?) 같습니다!

문제링크

import heapq

# 다익스트라
def dijkstra(node_dict, n, start, end):
    # 우선순위 queue 활용.
    heap = [(0, start)]
    # 거리 저장.
    dp = [1e9 for _ in range(n + 1)]
    dp[start] = 0

    # heap이 있을때
    while heap:
        # 우선순위가 높은 것 먼저 처리
        weight, now = heapq.heappop(heap)
        # 만약 이미 저장된 거리가 더 작은 경우 패스
        if dp[now] < weight:
            continue
        # 해당 노드에서 이어지는 간선확인
        for node, w in node_dict[now]:
            # 만약 지금 거리 + 다음 거리가 저장된 거리보다 작은 경우
            if dp[node] > weight + w:
                heapq.heappush(heap, (weight + w, node))
                dp[node] = weight + w
    return dp[end]

def solution(n, s, a, b, fares):

    answer = 1e9
    # 모든 노드 hash화
    node_dict = {i:[] for i in range(n+1)}
    # matrix를 hash로 변환
    for start, end, weight in fares:
        node_dict[start].append((end, weight))
        node_dict[end].append((start,weight))

    # 같이 택시타는 곳(모든 곳을 탐색)
    for i in range(1,n+1):
        
        if i == s:
            answer = min(answer, dijkstra(node_dict, n, s, a) + dijkstra(node_dict, n, s, b))

        elif i == a:
            dis_a = dijkstra(node_dict, n, s, a)
            if dis_a < answer:
                answer = min(answer, dis_a + dijkstra(node_dict, n, a, b))

        elif i == b:
            dis_b = dijkstra(node_dict, n, s, b)
            if dis_b < answer:
                answer = min(answer, dis_b + dijkstra(node_dict, n, b, a))
                
        else:
            dis_i = dijkstra(node_dict, n, s, i)
            if dis_i < answer:
                answer = min(answer, dis_i
                         + dijkstra(node_dict, n, i, a) + dijkstra(node_dict, n, i, b))

    return answer

문제 리뷰

1. 2021 카카오 블라인드 채용 1차 코딩테스트에서 1번 문제로 나온 문제로 이전에 풀었을 때는 단순하게 문제에서 요구하는 것을 하나씩 구현했습니다.
2. 이번 부스트캠프를 진행하면서 정규식 관련 수업이 있었습니다. 수업 내용을 조원들과 리뷰하던 중에 팀원분께서 말씀해주셨는데 해당 문제를 정규식으로 해결하면 쉽고 빠르게 풀 수 있다고 해서 공부한 것을 복습하는 겸해서 풀기고 했습니다.
3. 1차적으로 정규식으로 풀면서 어떻게 해야할 지 몰라서 for문과 if문으로 푼 것도 있었습니다..
4. 다른 분들의 정답을 보고 어떻게 해서 나왔는지 정리해서 풀었습니다. ^과 $로 시작과 끝의 .를 제거한 것과 \.+를 활용해서 반복되는 패턴을 잡는 방식도 있다는 것을 알게 됐습니다.

문제 링크

참고사이트

1차적으로 푼 것으로 if와 for문으로 찾은 경우도 있습니다.

import re

def solution(new_id):
    change_id = new_id
    # 1 단계
    change_id = change_id.lower()
    # 2 단계
    change_id = re.findall(r'[a-zA-Z0-9\-_.]',change_id)
    next_id = ""
    for i in change_id:
        next_id += i
    change_id = next_id
    # 3 단계
    change_id = re.sub(r"\.+",'.',change_id)
    # 4 단계
    if change_id:
        if change_id[0] == '.':
            change_id = change_id[1:]
    if change_id:
        if change_id[-1] == '.':
            change_id = change_id[:-1]
    # 5 단계
    if change_id == '':
        change_id = 'a'
    # 6 단계
    if len(change_id) >= 16:
        change_id = change_id[:15]
        if change_id[-1] == '.':
            change_id = change_id[:-1]
    if len(change_id) < 3:
        while len(change_id) < 3:
            change_id += change_id[-1]
    return change_id

2차적으로 푼 것으로 모든 단계를 정규식으로 해결했습니다.

def solution(new_id):
    st = new_id
    # 1단계
    # lower로 대문자 -> 소문자
    st = st.lower()

    # 2단계
    # ^은 not을 의미, [a-z, 0-9, -, _, .] 을 제외한 나머지 ''로 바꾸기
    st = re.sub('[^a-z0-9\-_.]', '', st)

    # 3단계
    # .이 1번 이상 반복되는 모든 글자를 '.'로 바꾸기
    # 여기서 \.+ 에서 \는 욕심없는 반복으로 변형, .이 있는 글자만 포함
    st = re.sub('\.+', '.', st)
    # \를 제외하면 .뒤의 모든 글자를 1개로 처리함.
    # st = re.sub('.+', '.', st)
    # +는 {1,}로 바꿀 수 있음. .{1,}는 .이 1번이상 반복되는 글자를 그룹화하는 것을 의미함.
    # st = re.sub('\.{1,}','.',st)

    # 4단계
    # ^[.]은 문자열 시작이 .로 시작하는 것을 의미
    # |은 or을 의미
    # [.]$sms 문자열 끝이 .로 끝나는 것을 의미
    st = re.sub('^[.]|[.]$', '', st)

    # 5단계, 6단계
    # 만약 0글자이면 'a'
    # 아니면 15까지, st가 15보다 작다면 끝까지 포함하기 때문에 :15까지 슬라이싱해도 끝까지 하는 것과 같음.
    st = 'a' if len(st) == 0 else st[:15]

    # 4단계 반복
    st = re.sub('^[.]|[.]$', '', st)

    # 7단계
    # 길이가 3보다 작다면 마지막 글자( == [-1])를 3 - len(st)만큼 반복해서 st에 붙임.
    st = st if len(st) > 2 else st + "".join([st[-1] for i in range(3-len(st))])
    return st

문제 리뷰

1. 작년에 코딩테스트를 하면서 스스로 많은 부족함을 느꼈고 그동안 공부를 열심히(..?) 해왔습니다! 그러다 프로그래머스에 문제가 나와있어서 지금 다시 풀어보면 풀 수 있을지 궁금해서 다시 풀어보고 리뷰하기로 결심했습니다!😀
2. 해당 문제는 코딩테스트에서 3번 문제로 나왔습니다. 다른 문제와 다르게 정확성과 효율성으로 나눠져있어서 정확성만 맞더라도 부분점수가 나옵니다. 작년에 시험볼 때에도 정확성은 통과했지만 효율성에서는.... 정답률을 보니 효율성 부분은 확실히 낮네용 4.49%.......
3. 단순하게 info와 query를 정리해서 문제를 풀면 정확성에서는 쉽게 해결할 수 있습니다! 하지만 효율성에서 맞기 위해서는 이분탐색을 활용해야 합니다. 대부분의 효율성 문제는 heap정렬과 이분탐색으로 해결가능한 것 같습니다.
4. 이분탐색을 하기 위해서는 info를 통해서 나올 수 있는 모든 조건을 정리해서 전부 입력하는 것입니다. 예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 됩니다.
5. 모든 조건들을 먼저 정리한 이후 오름차순으로 sorting을 합니다. 여기서 저는 높은 점수가 앞으로 오기 위해서 -1을 곱했습니다. 이유는 bisect_right를 하기 위해서 이고요.
6. info 정리가 끝났다면 이젠 query를 알맞게 가공한 다음 해당 query에서 점수를 이분탐색으로 찾으면 끝이 납니다.
7. 추가적으로 문제를 풀면서 4번 부분에서 처음에는 16가지 그룹을 구할 때, 조합을 활용해서 풀 때는 시간초과가 발생했지만 단순하게 16개를 추출하게 되면 통과됐습니다. 생각해보면 조합이 코드를 구현하거나 보여주기에는 더 깔끔하지만 효율적이지 않다고 생각이 들었습니다.

문제 링크

문제 링크와 카카오에서 제공해준 문제 해설 링크입니다.

from bisect import bisect_right

def get_type(type_arr):
    arr = []
    # 0개 '-'
    arr.append(tuple(type_arr))
    # 1개 '-'
    for i in range(4):
        temp = type_arr[:]
        temp[i] = '-'
        arr.append(tuple(temp))
    # 2개 '-'
    for i in range(4):
        for j in range(i+1, 4):
            temp = type_arr[:]
            temp[i] = '-'
            temp[j] = '-'
            arr.append(tuple(temp))
    # 3개 '-'
    for i in range(4):
        for j in range(i+1,4):
            for k in range(j+1,4):
                temp = type_arr[:]
                temp[i] = '-'
                temp[j] = '-'
                temp[k] = '-'
                arr.append(tuple(temp))
    # 4개 '-'
    arr.append(('-','-','-','-'))
    return arr

# 조합 구현
def comb(lst, n):
    arr = []
    if len(lst) < n:
        return arr

    if n == 1:
        for i in lst:
            arr.append([i])
    else:
        for i in range(len(lst)-n + 1):
            for temp in comb(lst[i+1:], n-1):
                arr.append([lst[i]] + temp)
    return arr

def solution(info, query):

    answer = [] # 결과값
    info_dict = {}  # info에 대한 정리.

    # info값 정리
    for i in info:

        info_arr = i.split()
        # 이분 탐색할 때 큰 값부터 시작하기 위해서 -1을 곱함.
        info_detail, info_score = [k for k in info_arr[:-1]], int(info_arr[-1]) * -1
        # 조합으로 16개를 구하는 방법.
        # info_dict[tuple(info_detail)] = info_dict.get(tuple(info_detail), []) + [info_score]
        # for j in range(1, 5):
        #     for temp in comb(info_detail, j):
        #         info_dict[tuple(temp)] = info_dict.get(tuple(temp), []) + [info_score]

        # 단순히 16개를 구하는 방법
        for i in get_type(info_detail):
            if i in info_dict:
                info_dict[i].append(info_score)
            else:
                info_dict[i] = [info_score]

    # 이분탐색을 하기위해서 sorting
    for key in info_dict.keys():
        info_dict[key].sort()

    # query문 계산
    for i in query:
        # and를 없애고 빈칸 기준으로 나누기
        query_arr = i.replace('and','').split()
        # 가장 마지막값은 제외하고 tuple로 만들고, score는 이분탐색시 빠르게 큰 값부터 시작해서 -1을 곱함.
        query_detail, qeury_score = tuple(k for k in query_arr[:-1]), int(query_arr[-1]) * -1

        # 해당 쿼리문이 없는 경우.
        if query_detail not in info_dict:
            answer.append(0)
        # 해당 쿼리문이 있는 경우 info_dict에서 쿼리문 찾은 이후
        # 이분탐색해서 해당 값이 들어갈 수 있는 가장 끝값 append에 추가하기
        else:
            answer.append(bisect_right(info_dict[query_detail], qeury_score))

    return answer

문제후기

1. 문제를 보고 DP를 활용하는 문제라고 판단했습니다.
2. 계산을 편하게 하기 위해서 좌표와 메트릭스의 크기를 동일하게 하고 계산했습니다.
3. 물 웅덩이가 없는 경우 해당 위치까지 똑같은 크기만큼 이동했기 때문에 비교할 필요 없이 더하면 됩니다.
4. 물 웅덩이가 있는 경우 값을 0으로 만들어 제외했습니다.

문제링크

def solution(m, n, puddles):

    # 매트릭스 제작.
    matrix = [[0] * (m + 1) for _ in range(n + 1)]

    # 출발, 집 좌표
    matrix[1][1] = 1

    # DP 시작
    for y in range(1, n + 1):
        for x in range(1, m + 1):
            # 출발 값
            if y == 1 and x == 1:
                continue
            # 웅덩이가 있는 경우 패쓰
            if [x, y] in puddles:
                matrix[y][x] = 0
            else:
                # 해당 위치 값은 이전값 2개의 합.
                matrix[y][x] = matrix[y - 1][x] + matrix[y][x - 1]

    return matrix[n][m] % 1000000007

문제후기

1. 문제에서 n이 1이상 100이하인 것과 경기 결과가 1개 이상 4,500개 이하인 것을 보고 완전탐색이 가능하다고 판단했습니다.
2. 입출력 예시에서처럼 5번 선수는 다른 선수와 경기를 하지 않아도 2번 선수를 통해서 결과를 유추할 수 있다는 것을 확인할 수 있습니다.
3. A선수가 B선수를 이기고 B 선수가 C선수를 이긴다면 A가 C를 이긴다는 조건이 성립합니다.( A>B이고 B > C이면 A>C)
4. 유추를 통해 이길 수 있는 선수와 지는 선수를 set 집합을 통해 저장 후 결과를 추출했습니다.

문제링크

def solution(n, results):
    # 선수 경기 결과 hash로 저장
    matrix = dict()

    # 이기는 사람 집합과 지는 사람 집합
    for i in range(1, n + 1):
        matrix[i] = [set(), set()]

    # 경기 결과 입력
    for i in results:
        matrix[i[0]][0].add(i[1])
        matrix[i[1]][1].add(i[0])

    # 만약 A > B 이고 B > C 인경우 A>C인 관계(>는 이긴다)
    # 모든 선수를 통해 경기하지 않아도 결과를 아는 경우 저장.
    for num, match in matrix.items():
        if match[0] and match[1]:
            for win in match[0]:
                matrix[win][1].update(match[1])
            for lose in match[1]:
                matrix[lose][0].update(match[0])

    # 만약 이기는 경우, 지는 경우, 자기 자신의 합이 모든 선수의 수인 경우 +1
    answer = 0
    for num, match in matrix.items():
        if len(match[0]) + len(match[1]) + 1 == n:
            answer += 1
    return answer
   

문제 후기

1. (만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.) 해당 제한사항을 가능한 이라는 것을 인지하지 못하고 단순하게 알파벳이 먼저 오면 해결하려 해서 틀리게 됐습니다.
2. DFS와 알파벳 순서 2가지를 생각해보며 다시 알고리즘을 짰고 스택을 활용하여 문제를 풀었습니다.
3. 해당 알고리즘의 경우 도착 or 항공편이 없는 경우 먼저 answer에 들어가게 했으며 마지막에 reverse를 통해 결과값을 제출했습니다.

출처 : programmers.co.kr/learn/courses/30/lessons/43164?language=python3

def solution(tickets):

    node_dict = {}      # 노드 hash화
    # 출발지를 key로 도착지를 value로 지정.
    for city in tickets:
        # dict.get(a,b) = dict에서 key가 a인 것을 찾고 없으면 b값을 넣겠다.
        node_dict[city[0]] = node_dict.get(city[0], []) + [city[1]]

    # 알파벳 역순으로 정렬
    for city in node_dict:
        node_dict[city] = sorted(node_dict[city], reverse=True)


    stack = ["ICN"]
    answer = []

    # 스택에 값이 있는동안 계속 반복
    while stack:
        now_city = stack[-1]
        # 만약 해당 도시 출발 항공표가 없을 때 answer에 추가.
        if now_city not in node_dict or node_dict[now_city] == []:
            answer.append(stack.pop())
        else:
            # 해당 도시 출발 항공표가 있을 때 다음 도시 pop해서 스택에 추가
            stack.append(node_dict[now_city].pop())
    # 역순이므로 다시 정렬
    answer.reverse()
    return answer

문제후기

1. operation에 들어있는 문자열을 판별하여 최대값과 최솟값을 찾아서 제외하고 결과적으로 최대값과 최솟값을 찾는 문제로 해석했습니다.
2. 파이썬에서 제공하는 heapq 모듈은 최소 힙을 기준으로 하므로 최대힙을 어떻게 처리할까 생각하다가 tuple로 최대힙을 만들어서 했습니다.
3. tuple로 최대힙을 만든경우 추출된 값을 다른 힙에서도 제외해야해서 시간이 오래걸린다는 것을 알고 nlargest 함수를 활용했습니다.

출처 : programmers.co.kr/learn/courses/30/lessons/42628?language=python3

import heapq


def solution(operations):
    min_heap = []       # 힙 입력 배열
    for i in operations:
        # 숫자 입력인 경우
        if i[0] == "I":
            num = int(i.split()[1])
            # 숫자를 heap에 push
            heapq.heappush(min_heap, num)
        # 최댓값 추출인 경우
        elif i == "D 1":
            # 배열 안에 값이 없으면 패쓰
            if min_heap:
                # nlargest로 가장 최댓값 추출
                min_heap.remove(heapq.nlargest(1, min_heap)[0])
        # 최솟값 추출인 경우
        elif i == "D -1":
            # 배열 안에 값이 없으면 패쓰
            if min_heap:
                # pop으로 최솟값 추출
                heapq.heappop(min_heap)
    # 배열에 값이 있는 경우 최댓값, 최솟값 추출
    # 없는 경우 [0,0]추출
    if min_heap:
        return heapq.nlargest(1, min_heap) + [heapq.heappop(min_heap)]
    return [0, 0]

문제 후기

1. 제한사항에서 n이 1,000,000,000을 확인하고 O(logN)을 확인했습니다.
2. 문제를 풀면서 어느 부분에서 이분탐색을 해야하는지 헤매다 최소공배수를 기준으로 잡고 적절한 위치를 이분탐색으로 찾으려했습니다. 해당 알고리즘의 경우 테스트케이스를 만족했지만 다른 케이스에서 전부 시간초과가 발생했습니다. 시간초과가 발생한 요인으로는 최소공배수를 찾고 배열을 만드는 과정에서 발생한다고 생각했습니다.
3. 제한시간을 초과하여 다른분의 블로그(wwlee94.github.io/category/algorithm/binary-search/immigration/)를 참조했습니다.
4. 최대값을 가장 오래걸리는 심사관이 모든 n명을 심사했을 경우로 하고 최소 시간을 탐색하며 진행했습니다.

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

def solution(n, times):
    answer = 0      # 정답값
    start = 1       # 최소 시작
    end = n * max(times)    # 최대 시작
    
    # 이분탐색 시작
    while start <= end:
        middle = (start + end) // 2
        
        # 해당 시간 동안 몇 명을 심사할 수 있는지
        count = 0
        for time in times:
            count += middle // time
        
        # n명 이상인 경우 end값 조정
        if count >= n:
            answer = middle
            end = middle - 1
        # n명 미만인 경우 start값 조정
        else:
            start = middle + 1
    return answer