231122 kakao2021 : re.sub문자변환, 조합의 개수, binary시간복잡도 최적화, 경유지확인+플로이드, 시간누적문제+dp+누적합활용

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/72410

신규 아이디 추천 (re.sub문자변환)

1번 문제는 가장 낮은 난이도에 해당하는 일명 몸풀기 문제입니다. 1단계~7단계에서 지시하는 그대로 구현하면 되기 때문에, 특별한 알고리즘보다는 정확한 구현이 필요한 문제입니다.

본 문제는 new_id의 길이가 1,000으로 매우 작습니다. 따라서, new_id의 길이를 n이라고 할 때, O(n^2) 성능의 알고리즘으로 구현해도 제한 시간 내 답을 구할 수 있습니다.

보다 효율적으로 구현한다면 O(n) 성능의 알고리즘으로 구현을 할 수도 있습니다. new_id에서 필요 없는 문자들을 직접 제거하지 말고, new_id를 앞에서부터 검사하면서 유효한 문자(제거되지 않아야 할 문자)만 추려서 새로운 문자열 변수(new_id_1)에 붙여나가는 방법을 사용하면 됩니다.

import re

def solution(new_id):

    # 1
    new_id = new_id.lower()

    # 2
    new_id = re.sub(r"[^a-z0-9\-\_\.]", "", new_id)

    # 3
    while ".." in new_id:
        new_id = new_id.replace("..", ".")

    # 4
    if new_id and new_id.startswith("."):
        new_id = new_id[1:]
    if new_id and new_id[-1] == ".":
        new_id = new_id[:-1]

    # 5
    if not new_id: new_id = "a"

    # 6
    if len(new_id) >= 16:
        new_id = new_id[:15]
        if new_id[-1] == ".":
            new_id = new_id[:14]

    # 7
    if len(new_id) <= 2:
        tmp = new_id[-1]
        while len(new_id) < 3:
            new_id += tmp

    answer = new_id
    return answer

정규표현식

https://hamait.tistory.com/342

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/72411

메뉴 리뉴얼 (조합의 개수)

먼저 문제에 대한 해답을 얻기 전에, 각 메뉴별로 가능한 모든 조합을 만들어 봅니다. 예를 들어 “ABCD”의 경우 다음과 같이 11가지 조합이 가능합니다.

“AB”, “AC”, “AD”, “BC”, “BD”, “CD”, “ABC”, “ABD”, “ACD”, “BCD”, “ABCD”

위와 같이 각 메뉴에서 가능한 모든 조합을 만들었다면, 각 조합의 개수를 세면 됩니다. 이때 “ABC”와 “CBA”를 같은 조합으로 세는 점을 주의해야 합니다. 쉽게 해결하는 방법으로는 처음에 각 문자열을 알파벳 순서로 정렬하거나, 만들어진 조합 문자열을 정렬하는 방법이 있겠습니다.

각 조합별로 개수를 셌다면, 최종적으로 문자열의 길이가 같은 조합 중 가장 많이 나타난 조합은 무엇인지 찾으면 됩니다.

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []
    for c in course:
        tmp = []
        for order in orders:
            combi = combinations(sorted(order), c)
            tmp += combi
        counter = Counter(tmp)
        if len(counter) != 0 and max(counter.values()) != 1:
            answer += ["".join(key) for key in counter if counter[key] == max(counter.values())]

    return sorted(answer)

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/72412

순위검색 (원본값을 찾으려는 값 기준 변환 + binary시간복잡도 최적화)

검색 조건이 “java and backend and junior and pizza 100″이라 하면, 위 지원자는 검색 대상에 포함되며, 검색 조건이 “java and – and junior and – 100” 인 경우에도 검색 대상에 포함이 됩니다.

따라서 모든 지원자들을 위와 같은 방식으로 분류한 후 같은 그룹의 지원자끼리 묶어두고, 해당 그룹에서 점수를 기준으로 오름차순 정렬해 둡니다.

이제, 검색 조건이 주어질 경우 INFO 배열에서 지원자들을 찾지 않고, 미리 분류해둔 그룹에서 X점 이상 맞은 지원자 수를 세주기만 하면 됩니다.

이때, X점 이상 맞은 지원자를 찾기 위해 해당 그룹의 최저점, 혹은 최고점부터 순차적으로 검색한다면 여전히 오랜 시간이 걸리게 됩니다. 이때, 숫자가 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있습니다. 이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound를 이용하면 됩니다.

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    answer = []

    # 주어진 점수로 만들 수 있는 모든 경우의 수 저장
    info_dict = dict()
    for i in range(len(info)):
        info_list = info[i].split()
        key = info_list[:-1]
        val = info_list[-1]

        # key로 만들 수 있는 모든 조합
        for j in range(5):
            for combi in combinations(key, j):
                tmp = "".join(combi)
                if tmp in info_dict:
                    info_dict[tmp].append(int(val))
                else:
                    info_dict[tmp] = [int(val)]
    # print(info_dict)

    # 점수 순으로 정렬
    for i in info_dict.keys():
        info_dict[i].sort()

    # 쿼리
    for q in query:
        tmp = q.split()
        q_key = tmp[:-1]
        q_val = tmp[-1]

        while 'and' in q_key:
            q_key.remove('and')
        while '-' in q_key:
            q_key.remove('-')

        # print(q_key)
        q_key = "".join(q_key)

        if q_key in info_dict:
            scores = info_dict[q_key]

            if scores:
                enter = bisect_left(scores, int(q_val))
                answer.append(len(scores) - enter)
        else:
            answer.append(0)

    return answer

시간복잡도X

def solution(info, query):
    table, scores = [], []

    for i in info:
        tmp = list(i.split())
        table.append(set(tmp[:-1] + ["-"]))
        scores.append(int(tmp[-1]))

    # print(table)
    # print(scores)

    answer = []
    for q in query:
        cnt = 0
        # q = q.replace("-", "")

        tmp = list(q.split(" and "))

        last = tmp.pop()
        food, score = last.split()
        tmp.append(food)

        for i in range(len(table)):
            if set(tmp).issubset(table[i]) and scores[i] >= int(score):
                cnt += 1

        answer.append(cnt)

    # TODO : 효율성 테스트 문제 해결
    return answer

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/72413?language=python3

합승 택시 요금(경유지확인+플로이드)

import sys

def ployd(n):
    global matrix
    for k in range(n):
        for i in range(n):
            for j in range(n):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

def solution(n, s, a, b, fares):
    global matrix
    matrix = [[sys.maxsize] * n for _ in range(n)]
    for i in range(n):
        matrix[i][i] = 0

    for fare in fares:
        u, v, w = fare
        matrix[u-1][v-1] = w
        matrix[v-1][u-1] = w

    ployd(n)
    answer = sys.maxsize
    for k in range(n):
        answer = min(answer, matrix[s-1][k] + matrix[k][a-1] + matrix[k][b-1])

    return answer

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/72414

광고 삽입 (시간누적문제+dp+누적합활용)

def convert(time):
    H, m, s = map(int, time.split(":"))
    s += 3600 * H + m * 60
    return s

def convert_origin(time):
    h = time // 3600
    h = '0' + str(h) if h < 10 else str(h)
    time = time % 3600
    m = time // 60
    m = '0' + str(m) if m < 10 else str(m)
    time = time % 60
    s = '0' + str(time) if time < 10 else str(time)
    return h + ':' + m + ':' + s

def solution(play_time, adv_time, logs):
    play_time = convert(play_time)
    adv_time = convert(adv_time)

    dp = [0] * (play_time + 1)

    for log in logs:
        start, end = log.split("-")
        dp[convert(start)] += 1
        dp[convert(end)] -= 1

    # 누적합
    # 구간별 시청 수 기록
    for i in range(1, len(dp)):
        dp[i] = dp[i] + dp[i-1]

    # 모든 시청 수 기록
    for i in range(1, len(dp)):
        dp[i] = dp[i] + dp[i-1]

    most_view = 0
    max_time = 0

    for i in range(adv_time - 1, play_time):
        if i >= adv_time:
            # 이 구간의 누적 시청자 수 : i의 누적 시청사 수 - i-adv_time의 누적 시청자 수
            if most_view < dp[i] - dp[i - adv_time]:
                most_view = dp[i] - dp[i - adv_time]
                max_time = i - adv_time + 1
        else:
            if most_view < dp[i]:
                most_view = dp[i]
                max_time = i - adv_time + 1

    answer = convert_origin(max_time)

    return answer

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/72415

카드 짝 맞추기 (카드짝맞추기+구현)

카드 종류가 최대 6개이므로, 어떤 카드부터 제거해 나갈지 정하는 방법은 6! 가지입니다. 예를 들어 카드가 3종류인 경우, 3종류 카드를 제거하는 순서는 다음과 같이 6가지입니다.

1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1

위와 같이 카드를 제거하는 모든 순서에 대해서 각각 카드를 제거해 보고, 그중 키 조작 횟수가 가장 적은 방법을 찾으면 됩니다. 이때, 각 카드는 종류별로 2장씩이므로, 두 카드를 제거하는 순서에 따라 키 조작 횟수가 달라질 수 있음을 주의합니다. 즉, 현재 제거해야 되는 카드 번호 X에 대해서, 카드 하나를 XA, 다른 카드 하나를 XB라고 했을 때 다음 두 가지 경우에 대해 고려해 주면 됩니다.

현재 커서 위치 → XA 카드를 제거 → XB 카드를 제거 현재 커서 위치 → XB 카드를 제거 → XA 카드를 제거

만약 XB 카드를 나중에 제거했고, X 카드 다음으로 Y 카드를 제거해야 한다면 이번에는 다음과 같이 두 가지 경우를 고려합니다.

현재 커서 위치(XB 카드 위치) → YA 카드를 제거 → YB 카드를 제거 현재 커서 위치(XB 카드 위치) → YB 카드를 제거 → YA 카드를 제거

따라서 위와 같은 방법으로 카드를 제거하는 가능한 모든 방법을 고려해 주면 되며, “현재 커서 위치 → XA 카드를 제거”와 같이 커서를 이동시키는 최소 조작 횟수는 BFS 탐색을 이용하여 최단거리를 구하면 됩니다.

from collections import deque
from itertools import permutations
from copy import deepcopy

board = []
def ctrl_move(r, c, k, t):
    global board
    cr, cc = r, c
    while True:
        nr = cr + k
        nc = cc + t
        if not (0<=nr<4 and 0<=nc<4):
            return cr, cc
        if board[nr][nc] != 0:
            return nr, nc
        cr = nr
        cc = nc

def bfs(start, end):
    r, c = start
    find_r, find_c = end
    queue = deque()
    queue.append((r, c, 0))
    visited = [[0]*4 for _ in range(4)]
    move = [(0,-1),(0,1),(-1,0),(1,0)]
    while queue:
        r, c, temp = queue.popleft()
        if visited[r][c]: continue
        visited[r][c] = 1
        if r == find_r and c == find_c:
            return temp
        for k, t in move:
            cr = k+r
            cc = c+t
            if 0<=cr<4 and 0<=cc<4:
                queue.append((cr,cc, temp+1))
            cr, cc = ctrl_move(r, c, k, t)
            queue.append((cr, cc, temp+1))
    return -1

def solution(input_board, sr, sc):
    global board
    board = input_board
    location = [[] for _ in range(7)]
    nums = []
    for i in range(4):
        for j in range(4):
            if board[i][j]:
                if board[i][j] not in nums: nums.append(board[i][j])
                location[board[i][j]].append((i, j))

    # 카드를 선택하는 모든 경우 탐색
    per = list(permutations(nums, len(nums))) # 순열
    answer = float('inf')
    for i in range(len(per)):
        board = deepcopy(input_board) # 지웠던 곳 다시 채우기
        cnt = 0
        r, c = sr, sc
        for j in per[i]:
            # 동일한 카드 중 어느 카드 부터 뽑는지에 따라 탐색하는 횟수가 달라짐
            left = bfs((r, c), location[j][0])
            right = bfs((r, c), location[j][1])
            # 더 적은 횟수를 탐색한 곳을 기준으로 횟수 추가 및 위치 설정
            if left < right:
                cnt += left
                cnt += bfs(location[j][0], location[j][1])
                r, c = location[j][1]
            else:
                cnt += right
                cnt += bfs(location[j][1], location[j][0])
                r, c = location[j][0]
            board[location[j][0][0]][location[j][0][1]] = 0 # 카드 지우기
            board[location[j][1][0]][location[j][1][1]] = 0 # 카드 지우기
            cnt += 2 # enter
        answer = min(answer, cnt)
    return answer

[robert-min]

매출 하락 최소화

DP 문제. 한 서브트리에서 팀장(루트 노드)과 팀원(자식 노드)들의 참여하였을 때의 매출 합계를 DP[node][i]라 하자. i == 0이면 이 노드는 참여하지 않는 것이고, i == 1 이면 이 노드는 참여하는 것이다. 모든 DP 내 node값의 초기값은 [0, sales[node]]가 될 것이다. 이제 이를 팀장의 입장에서 생각해 보자.  

i == 1 : 팀장은 무조건 참여하는 게 확정이므로, 이미 전제조건인 최소 참여 인원은 확정되었다. 따라서 각 자식 DP값의 최솟값의 합을 더해 주면 된다. i == 0 : 팀장이 참여하지 않는 경우이다. 앞선 i == 1인 케이스와 같이 최솟값의 합을 구해 주자.

그런데, 모든 리프값의 최솟값이 자식 노드가 참여하지 않을 때 (DP[leaf][0])가 될 때가 있다. 이 경우는 팀장을 포함한 모든 구성원이 참여하지 않는 셈이므로 조건을 만족할 수 없다. 따라서 자식 노드 중 한 명이 참여해야 한다. 이에 따라 i == 0을 구할 때는, 최솟값과 최댓값의 차가 가장 작은 리프를 저장해야 한다. 이 리프를 저장함으로써 두 번째 최솟값을 저장하는 효과를 가질 수 있다. 만약 각 자식 DP값의 최솟값이 모두 참여하지 않을 때라면, 앞서 저장한 리프 노드를 이용해 최솟값을 최댓값으로 교체한다.

이 규칙에 따라 DP값을 DFS로 구하면, 모든 서브트리에 대한 최적해 및 전체 트리의 최적해를 구할 수 있다.  

init : links를 edge_dict으로 변환한다. edge_dict는 어떤 서브트리의 루트 노드를 키값으로, 그리고 자식 노드 리스트를 value값으로 가진다. dfs : 전체 트리를 재귀적으로 탐색한 다음, 위의 묘사한 조건에 따라 DP값을 업데이트한다. 주의할 점은, 평균 매출값 sales[node]가 0일 때가 존재한다. 즉 이 경우는 DP[node][0] == DP[node][1]인 예외상황이 발생할 수 있으므로, 확실히 DP[node][0] < DP[node][1]일 때만 체크하도록 한다. solution : 메인함수. init으로 생성되는 edge_dict를 이용하여 dfs를 수행한 후, 루트 노드의 DP값 DP[1]의 최솟값을 반환한다.

from collections import defaultdict

def init(links):
    edge_dict = defaultdict(list)

    for a, b in links:
        edge_dict[a].append(b)
    return edge_dict

def dfs(node, edge_dict, dp):
    if not edge_dict[node] :
        return

    cnt, zero_cnt, min_val, min_diff = 0, 0, 0, float('inf')
    for leaf in edge_dict[node] :
        dfs(leaf, edge_dict, dp)
        min_val += min(dp[leaf])
        cnt += 1
        if dp[leaf][0] < dp[leaf][1] :
            zero_cnt += 1
            min_diff = min(min_diff, dp[leaf][1] - dp[leaf][0])

    dp[node][1] += min_val
    dp[node][0] += min_val + min_diff if cnt == zero_cnt else min_val

def solution(sales, links):

    dp = [[0, 0]] + [[0, sale] for sale in sales]

    edge_dict = init(links)
    dfs(1, edge_dict, dp)
    answer = min(dp[1])
    return answer