코드

def solution(n, k, cmd):
    answer = {x: ["O", x - 1, x + 1] for x in range(-1, n + 1)}
    deleted = []

    for c in cmd:
        if c[0] == 'U':
            i = int(c.split()[1])
            for _ in range(i):
                k = answer[k][1]
        elif c[0] == "D":
            i = int(c.split()[1])
            for _ in range(i):
                k = answer[k][2]
        elif c[0] == "C":
            answer[k][0] = "X"
            bef, nxt = answer[k][1], answer[k][2]
            answer[bef][2] = nxt
            answer[nxt][1] = bef
            deleted.append(k)
            k = bef if answer[k][2] == n else nxt
        else:
            removed = deleted.pop()
            answer[removed][0] = "O"
            bef, nxt = answer[removed][1], answer[removed][2]
            answer[removed][1] = bef
            answer[removed][2] = nxt
            answer[bef][2] = removed
            answer[nxt][1] = removed

    return ''.join(map(lambda x: answer[x][0], range(n)))

리뷰

• 처음에 연결 리스트를 고려하지 않았던 이유는 연결 리스트로 만들더라도 처음에서 끝으로 계속 커서를 이동시키면 시간복잡도를 만족시키지 못한다고 생각했기 때문이었다.

• 하지만 조건에 "cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다."라는 조건이 있기 때문에 연결 리스트를 이용하는 방법은 시간복잡도를 충족한다.
• 문자열을 숫자로 바꾸는 과정에서 2자리 이상의 숫자를 고려하지 않고 i = int(c[2])를 써서 나중에 런타임 에러(Out of range)가 발생했다. 문자열을 숫자로 바꾸는 것을 조심해야겠다.

코드

def solution(info, edges):
    graph = {x: set() for x in range(len(info))}
    for s, d in edges:
        graph[s].add(d)
        graph[d].add(s)


    def backtracking(cur, visited, adj, nsheep, nwolf):
        if info[cur] == 0:
            nsheep += 1
        else:
            nwolf += 1

        if nsheep <= nwolf:
            return nsheep

        visited = visited | {cur}
        adj = (adj | graph[cur]) - visited

        if not adj:
            return nsheep
        return max(map(lambda x: backtracking(x, visited, adj, nsheep, nwolf), adj))


    return backtracking(0, set(), set(), 0, 0)

리뷰

• 어려운 문제는 아니었지만 쉽게 구현하지 못하고 햇갈렸다.

코드

MAX = 987654321

def solution(alp, cop, problems):
    galp = max(max([x[0] for x in problems]), alp)
    gcop = max(max([x[1] for x in problems]), cop)

    problems = [[0, 0, 1, 0, 1], [0, 0, 0, 1, 1]] + problems
    dp = [([MAX] * (gcop + 1)) for _ in range(galp + 1)]
    dp[alp][cop] = 0

    for calp in range(alp, galp + 1):
        for ccop in range(cop, gcop + 1):
            solvable = list(filter(lambda x: x[0] <= calp and x[1] <= ccop, problems))
            for _, _, ralp, rcop, cost in solvable:
                nalp = min(calp + ralp, galp)
                ncop = min(ccop + rcop, gcop)
                ncost = dp[calp][ccop] + cost

                dp[nalp][ncop] = min(dp[nalp][ncop], ncost)

    return dp[galp][gcop]

리뷰

• 처음 문제를 보았을 때 어떤 식으로 풀어야 될지 감을 잡지 못했고 해설을 보고 DP 문제라는 것을 알고 나서야 풀 수 있었다. PS 경험의 부족이라고 느꼈고 더 많은 문제를 풀어봐야 겠다

• 처음 문제를 풀고 채점했을 때 런타임 에러가 발생했다. 런타임 에러를 보고 index out of range라고 추측했고, 어떤 상황에서 해당 오류가 발생할 수 있을지 고민하다 보니 초기값이 실제 값보다 큰 경우를 고려하지 않았다는 것을 깨달았다. 오류를 해결하는 접근 방식이 좋았다고 느꼈다.

코드

from heapq import heappush, heappop

MAX = 987654321

def solution(n, paths, gates, summits):
    graph = {x: [] for x in range(1, n + 1)}
    for s, d, w in paths:
        graph[s].append((d, w))
        graph[d].append((s, w))

    summits = set(summits)
    intensities = [MAX] * (n + 1)
    pq = []

    for gate in gates:
        heappush(pq, (gate, 0))
        intensities[gate] = 0

    while pq:
        node, intensity = heappop(pq)
        # intensity > intensities[node]: 더 작은 값이 먼저 실행된 경우
        if (node in summits) or (intensity > intensities[node]):
            continue

        for d, w in graph[node]:
            new_intensity = max(intensity, w)
            if intensities[d] > new_intensity:
                intensities[d] = new_intensity
                heappush(pq, (d, new_intensity))

    return min(map(lambda x: [x, intensities[x]], summits), key = lambda x: (x[1], x[0]))

문제 해설 참고 블로그

리뷰

• 변형된 다익스트라 알고리즘을 사용하면 풀 수 있을 것이라는 생각은 했지만 heap을 이용하지 않으면 시간 초과가 났다. 다익스트라 알고리즘에 대해 복습이 필요할 것 같다

• 산봉우리의 값만이 중요하기 때문에 입구부터 시작하면 intesity 결과가 산봉우리에 남아서 편하게 풀 수 있지만 반대로 산봉우리부터 시작해서 어디서부터 시작했는지 또 기록해야 되는 문제가 있었다

코드

def solution(n, m, x, y, r, c, k):
    # dlru
    nm = [0] * 4
    if x > r:
        nm[3] = x - r
    else:
        nm[0] = r - x
    if y > c:
        nm[1] = y - c
    else:
        nm[2] = c - y

    left = k - sum(nm) 
    if left < 0 or left % 2 == 1:
        return "impossible"
    left //= 2

    mx = n - max(x, r)
    my = min(y, c) - 1

    l = [0] * 3
    if mx > left:
        l[0] = left
    else:
        l[0] = mx
        left -= mx

    if my > left:
        l[1] = left
    else:
        l[1] = my
        left -= my
        l[2] = left

    return 'd' * (nm[0] + l[0]) + 'l' * (nm[1] + l[1]) + 'rl' * l[2] + 'r' * (nm[2] + l[1]) + 'u' * (nm[3] + l[0])

리뷰

• 문제를 풀기 전에 손으로 그려보면서 어떤 상황인지 생각하고 푸는 것이 중요하다는 것을 다시 한번 느꼈다

코드

def solution(commands):
    answer = []

    cells = []
    for command in commands:
        cmd = command.split()
        if cmd[0] == "UPDATE":
            if len(cmd) == 4:


                def update1(r, c, v):
                    for cell in cells:
                        if (r, c) in cell[0]:
                            cell[1] = v
                            return

                    cells.append([{(r, c)}, v])


                update1(int(cmd[1]), int(cmd[2]), cmd[3])
            else:


                def update2(v1, v2):
                    for cell in cells:
                        if cell[1] == v1:
                            cell[1] = v2


                update2(cmd[1], cmd[2])
        elif cmd[0] == "MERGE":


            def findcell(r, c):
                for i, cell in enumerate(cells):
                    if (r, c) in cell[0]:
                        return cells.pop(i)
                return [{(r, c)}, "EMPTY"]


            def merge(r1, c1, r2, c2):
                cell1 = findcell(r1, c1)
                cell2 = findcell(r2, c2)
                if cell1[1] == "EMPTY":
                    cell1[1] = cell2[1]

                cells.append([cell1[0] | cell2[0], cell1[1]])


            merge(int(cmd[1]), int(cmd[2]), int(cmd[3]), int(cmd[4]))
        elif cmd[0] == "UNMERGE":


            def unmerge(r, c):
                for cell in cells:
                    if (r, c) in cell[0]:
                        cell[0] = {(r, c)}
                        return


            unmerge(int(cmd[1]), int(cmd[2]))
        else:


            def printf(r, c):
                for cell in cells:
                    if (r, c) in cell[0]:
                        return cell[1]
                return "EMPTY"


            answer.append(printf(int(cmd[1]), int(cmd[2])))

    return answer

리뷰

• 단순 구현 문제였지만 셀을 저장하기 위한 구조를 정하는 것이 어려웠다
  • 처음에는 50 * 50 표에서 child cell이 parent cell을 참조하는 구조로 구현하려고 했지만 unmerge에서 child cell을 찾는 과정이 어려웠다
  • 그래서 cell group을 set으로 저장하는 리스트를 만들었더니 더 쉽게 풀렸다

코드

def solution(numbers):
    binarys = list(map(lambda x: bin(x)[2:], numbers))
    full_binarys = list(map(insert_dummy, binarys))
    return list(map(lambda x: 1 if validate(x) else 0, full_binarys))


def insert_dummy(s):
    l = len(s)
    x = 1
    while x - 1 < l:
        x *= 2
    return "0" * (x - l - 1) + s


def validate(tree):
    if "1" not in tree:
        return True

    mid = len(tree) // 2
    if tree[mid] != "1":
        return False

    return validate(tree[:mid]) and validate(tree[mid + 1:])

리뷰

• 문제의 핵심은 더미 노드 아래에 실제 노드가 있으면 안된다는 것이다

• 따라서 먼저 포화 트리를 만든 후, 루트 노드(중간값)을 확인하고, 1이면 좌우 서브트리에 대해 다음과 같은 과정을 반복했다

코드

def solution(users, emoticons):
    rates_list = all_rates(len(emoticons))

    max_plus = max_price = 0
    for rates in rates_list:
        plus = price = 0
        for user in users:
            p = calculate(user[0], rates, emoticons)
            if p >= user[1]:
                plus += 1
            else:
                price += p

        if plus > max_plus or (plus == max_plus and price > max_price):
            max_plus = plus
            max_price = price

    return [max_plus, max_price]


def all_rates(l):
    cases = []
    rates = [10, 20, 30, 40]


    def all_cases(picked, left):
        if not left:
            cases.append(picked)
            return

        for r in rates:
            all_cases(picked + [r], left - 1)


    all_cases([], l)
    return cases


def calculate(standard, rates, prices):
    total_price = 0
    for i, r in enumerate(rates):
        if r >= standard:
            total_price += prices[i] * (100 - r) / 100

    return total_price

리뷰

• case를 모두 구하는 방법은 itertools.product를 이용하면 쉽게 할 수 있다

• 처음에 할인률이 10%, 20%, 30%, 40%만 가능하다는 지문을 못읽고 헤맸다

코드

def solution(cap, n, deliveries, pickups):
    answer = 0

    ddist = convert(deliveries)
    pdist = convert(pickups)

    didx = len(ddist) - 1
    pidx = len(pdist) - 1

    while didx >= 0 or pidx >= 0:
        dval = ddist[didx] if didx >= 0 else 0
        pval = pdist[pidx] if pidx >= 0 else 0
        answer += max(dval, pval)

        didx -= cap
        pidx -= cap

    return answer * 2


def convert(arr):
    converted = []
    for i, v in enumerate(arr):
        converted += [i + 1] * v
    return converted

리뷰

• 결국 문제를 요약하면 모든 택배를 배달/수거할 때까지, 가장 먼곳부터 택배를 배달/수거하면 된다.

• 결국 얼마만큼 거리에 몇개의 택배가 있는지 여부가 중요하기 때문에 ddist, pdist라는 값에 거리라는 값을 개수만큼 넣어주고, n개씩 끊어서 더 먼 거리만큼 answer에 더하는 방식을 이용했다.
• 처음에는 배열을 자르고, 두 배열이 모두 빌 때까지 반복하는 방식을 이용했지만 시간 초과가 나서 배열을 건들지 않고 인덱스만 바꾸는 방식으로 변경했다.
• 아이디어가 약간 필요했던 풀이였기 때문에 실제 문제로 나왔을 때 풀 수 있을지 확신할 수 없다. 최대한 많은 경험을 해보는 것이 좋겠다.

코드

from collections import defaultdict

def solution(str1, str2):
    dict1 = get_dictionary(str1)
    dict2 = get_dictionary(str2)

    inter_keys = set(dict1.keys()) & set(dict2.keys())
    inter = {x: min(dict1[x], dict2[x]) for x in inter_keys}

    sum_keys = set(dict1.keys()) | set(dict2.keys())
    sums = {x: max(dict1[x], dict2[x]) for x in sum_keys}

    if len(sums) == 0:
        return 65536
    return int((sum(inter.values()) / sum(sums.values())) * 65536)


def get_dictionary(s):
    s = s.lower()
    arr = [x + y for x, y in zip(s[:-1], s[1:])]
    dic = defaultdict(int)

    for v in arr:
        if not v.isalpha():
            continue
        if v in dic:
            dic[v] += 1
        else:
            dic[v] = 1
    return dic

리뷰

• defaultdict의 사용법에 대해 알아봐야겠다.

• 다른 사람들의 풀이에서는 dictionary를 만들지 않고 set으로 만든 후, 리스트에서 원소의 개수를 세는 방식을 이용했다. 풀이는 훨씬 간단해 보이지만 set을 이용한 풀이는 원소의 개수를 세는 과정에서 O(n^2)의 시간 복잡도를 가지지만 내 풀이는 dictionary로 변환하는 과정에서 한번만 순회하기 때문에 O(n)의 시간 복잡도를 가진다.

코드

def solution(m, musicinfos):
    musics = []
    for music in musicinfos:
        start, end, title, content = music.split(",")
        time = duration(start, end)
        musics.append((title, full(mapping(content), time)))
    musics.sort(key = lambda x: -len(x[1]))

    m = mapping(m)
    for music in musics:
        if m in music[1]:
            return music[0]
    return "(None)"


def duration(start, end):
    s_h, s_s = map(int, start.split(":"))
    e_h, e_s = map(int, end.split(":"))
    return (e_h - s_h) * 60 + (e_s - s_s)


def mapping(content):
    mapped = {
        "C#": "c",
        "D#": "d",
        "F#": "f",
        "G#": "g",
        "A#": "a"
    }
    for m in mapped:
        content = content.replace(m, mapped[m])
    return content


def full(content, time):
    l = len(content)
    return content * (time // l) + content[:time % l]

리뷰

• #을 생각하다 보니 자연스럽게 정규식이 먼저 생각났다. 단순히 #이 붙은 문자들을 다른 문자로 치환하면 된다는 사실을 생각해내지 못했다.

• 정렬 순서도 오름차순이면 -를 붙혀야되는데 실수를 찾아내지 못했다.

코드

def solution(msg):
    answer = []
    dict = {chr(ord('A') + i): (i + 1) for i in range(26)}
    cur = ''
    for m in msg:
        cur += m
        if cur not in dict:
            dict[cur] = len(dict) + 1
            answer.append(dict[cur[:-1]])
            cur = m
    if cur:
        answer.append(dict[cur])

    return answer

코드

def solution(files):
    seperated_files = list(map(lambda x: seperate(x), files))
    sorted_files = sorted(seperated_files, key = lambda x: (x[0].lower(), int(x[1])))
    return list(map(lambda f: "".join(f), sorted_files))

def seperate(file): 
    n_start = -1
    n_end = len(file)
    for i, f in enumerate(file):
        if f.isdigit() and n_start == -1:
            n_start = i
        elif n_start != -1 and not f.isdigit():
            n_end = i
            break
    return (file[:n_start], file[n_start:n_end], file[n_end:])

리뷰

• seperate() 함수는 정규표현식을 이용하면 더 쉽게 할 수 있다

코드

def solution(record):
    answer = []
    nickname = {}        # key = uid, value = nickname

    for rec in record:
        temp = list(rec.split())
        if len(temp) == 3:
            nickname[temp[1]] = temp[2]

    for rec in record:
        temp = list(rec.split())
        if temp[0] == "Enter":
            answer.append(f"{nickname[temp[1]]}님이 들어왔습니다.")
        elif temp[0] == "Leave":
            answer.append(f"{nickname[temp[1]]}님이 나갔습니다.")

    return answer

리뷰

• 문제를 읽고 사용자가 들어오거나 닉네임이 변경될 때마다 기존 배열을 확인하지만 않으면 시간 초과가 나지 않을 것이라고 생각했다. 구현도 간단한 편이었기 때문에 굳이 최적화하려고 노력하지 않고 가장 간단한 방법으로 빠르게 푸는 방법을 선택했다.

코드

def solution(relation):
    cases = create_cases(len(relation[0]))
    unique_key = get_candidates(relation, cases)
    return len(unique_key)


def create_cases(length):
    cases = []
    for i in range(1, length + 1):


        def pick(picked, left, length):
            if len(picked) == length:
                cases.append(picked)
                return
            if left:
                pick(picked, left[1:], length)
                pick(picked | {left[0]}, left[1:], length)


        pick(set(), [i for i in range(length)], i)
    return cases


def get_candidates(relation, cases):
    candidates = []
    while cases:
        key = cases.pop(0)
        if is_unique(relation, key):
            candidates.append(key)

            temp = []
            for case in cases:
                if not case > key:
                    temp.append(case)
            cases = temp

    return candidates


def is_unique(relation, case):
    row = list(map(lambda x: tuple([x[i] for i in case]), relation))
    return len(row) == len(set(row))

리뷰

• 모든 케이스를 구한 다음에 이 케이스가 후보키의 조건을 만족하는지 확인하는 방식으로 풀었다.

• itertools의 combination 함수를 이용하면 더 쉽게 모든 케이스를 구할 수 있다.

코드

def solution(s):
    answer = 1000
    for l in range(1, len(s) + 1):
        answer = min(answer, length(s, l))
    return answer


def length(s, l):
    arr = []
    while s:
        arr.append(s[:l])
        s = s[l:]

    memory = [[arr[0], 1]]
    for v in arr[1:]:
        if memory[-1][0] == v:
            memory[-1][1] += 1
        else:
            memory.append([v, 1])

    result = 0
    for s, n in memory:
        result += len(s) + (len(str(n)) if n != 1 else 0)

    return result

리뷰

• 처음에 문제를 꼼꼼하게 읽지 못해서 앞에서부터 자르는 것을 알지 못하고 풀어서 시간을 좀 낭비했다. 문제를 잘 읽고 풀어야겠다

• 같은 단어가 10개 이상 나오면 숫자가 2자리가 된다는 것을 전혀 생각하지 못했다.

코드

def solution(p):
    return seperate(p)


def seperate(string):
    if string == '':
        return string

    correct = True if string.startswith('(') else False
    idx = 0
    diff = 1 if correct else -1
    while diff:
        idx += 1
        diff += 1 if string[idx] == '(' else -1

    if correct:
        return string[:idx + 1] + seperate(string[idx + 1:])
    else:
        return f'({seperate(string[idx + 1:])}){flip(string[1:idx])}'


def flip(string):
    return "".join(map(lambda x: '(' if x == ')' else ')', string))

리뷰

• 문제에서 시키는 대로만 하면 풀릴 것이라고 생각해서 바로 코드 작성을 시작했는데 풀다보니 햇갈렸다. 결국 차분하게 수도코드부터 작성하고 다시 풀었더니 쉽게 풀렸다. 쉬워 보이는 문제라도 꼭 수도코드를 먼저 작성하는 습관들 들여야겠다.

• 아무래도 자주 사용하는 언어가 파이썬이 아니다 보니 문자열 처리와 같은 문법이 조금 약한 것 같다. 익숙하지 않은 문법들을 정리해두고 익숙해질 때까지 연습해야겠다.

코드

def solution(s):
    result = sorted(list(map(lambda x: set(map(int, x.split(","))), s[2:-2].split("},{"))))
    answer = [result[0]]
    for v1, v2 in zip(result[1:], result[:-1]):
        answer.append(v1 - v2)

    return list(map(lambda x: x.pop(), answer))

리뷰

• 집합 형태의 문자열을 모두 집합으로 변환한 다음 차집합을 이용해서 풀었다.

• 아래 코드와 같이 최대한 줄여봤지만 위의 코드가 더 가독성이 좋은 것 같다.

  def solution(s):
    result = sorted(list(map(lambda x: set(map(int, x.split(","))), s[2:-2].split("},{"))))        
    return list(result[0]) + [(v1 - v2).pop() for v1, v2 in zip(result[1:], result[:-1])]

코드

def solution(expression):
    ops = {"+", "-", "*"}
    orders = [
        ["+", "-", "*"], 
        ["+", "*", "-"], 
        ["-", "+", "*"], 
        ["-", "*", "+"], 
        ["*", "+", "-"], 
        ["*", "-", "+"]
    ]

    numbers = []
    operators = []
    before = 0
    for cur in range(len(expression)):
        if expression[cur] in ops:
            numbers.append(int(expression[before:cur]))
            operators.append(expression[cur])
            before = cur + 1
    numbers.append(int(expression[before:]))

    answer = 0
    for order in orders:
        nums = numbers[:]
        ops = operators[:]
        while order:
            op = order.pop()
            while op in ops:
                idx = ops.index(op)
                ops.pop(idx)
                n1 = nums.pop(idx)
                n2 = nums.pop(idx)

                if op == "+":
                    nums.insert(idx, n1 + n2)
                elif op == "-":
                    nums.insert(idx, n1 - n2)
                else:
                    nums.insert(idx, n1 * n2)

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

    return answer

리뷰

• 연산자 우선순위의 종류가 6개밖에 안되기 때문에 단순 구현 문제라고 생각했다. 처음 생각했던 것처럼 숫자와 연산자들을 나누고, 우선순위가 높은 연산자부터 계산하는 방식으로 풀었다.

• 중간에 deepcopy 관련 문제가 발생했다. collections을 복사할 때에는 항상 신경써야겠다.
• 다른 사람들의 풀이를 보니 문자열을 split하고 join하면서 간결하게 구현한 코드를 찾을 수 있었다. 문자열을 처리하는 방법 중 하나로 자주 사용되는 것 같다.
• eval() 이라는 함수는 수식이 적혀있는 문자열을 실행시키는 함수이다. 하지만 검색해본 결과 큰 보안문제가 있기 때문에 코딩테스트에서만 사용하고 프로덕트 코드에서는 사용하면 안된다. 링크

코드

def solution(orders, course):
    answer = []
    dishes_sets = [{d for d in o} for o in orders]

    for c in course:
        max_size = 0
        max_cases = []
        memory = {}

        for o in orders:
            sorted_order = sorted(o)

            def create_all_cases(order, count):
                result = []


                def recursive(picked, idx):
                    if len(picked) == count:
                        result.append(picked)
                        return

                    if idx >= len(order):
                        return

                    recursive(picked + order[idx], idx + 1)
                    recursive(picked, idx + 1)                        


                recursive("", 0)
                return result


            cases = create_all_cases(sorted_order, c)
            for case in cases:
                if case not in memory:
                    count = len(list(filter(lambda x: {c for c in case} <= x, dishes_sets)))
                    memory[case] = count
                    if max_size < count:
                        max_size = count
                        max_cases = [case]
                    elif max_size == count:
                        max_cases.append(case)

        if max_size > 1:
            answer += max_cases

    return sorted(answer)

리뷰

collections와 itertools를 이용하면 아래의 풀이와 같이 정말 간단하게 풀 수 있다. 하지만 라이브러리를 몰라도 구현으로 충분히 풀 수 있는 문제고 모든 라이브러리를 다 알 수는 없기 때문에 내가 푼 풀이도 나쁘지는 않다고 생각한다. 다만 collections와 itertools는 많이 활용되는 라이브러리이기 때문에 시간 내어 자주 쓰는 함수들을 정리하면 좋겠다. 그것보다 시간복잡도를 통해 완전 탐색 문제라는 것을 빠르게 알아차리지 못하고 다른 방법을 생각하기 위해서 고민했던 것이 아쉽다. 시간복잡도를 어림하는 것을 더 연습해야겠다.

import collections
import itertools

def solution(orders, course):
    result = []

    for course_size in course:
        order_combinations = []
        for order in orders:
            order_combinations += itertools.combinations(sorted(order), course_size)

        most_ordered = collections.Counter(order_combinations).most_common()
        result += [ k for k, v in most_ordered if v > 1 and v == most_ordered[0][1] ]

    return [ ''.join(v) for v in sorted(result) ]

풀이 링크