a = [1, 2, 3]
b = a
c = a[:]  # copy
print(id(a))  # 1991522371976
print(id(b))  # 1991522371976, same address
print(id(c))  # 1991521639688, copy 된 새 객체

a = [1, 2, 3]
d = a.copy()
print(id(d))  # 1991522268808, copy() 메서드 활용

import copy


a = [1, 2, [3, 4], 5]
b = a.copy()  # 단순 copy
c = copy.deepcopy(a)  # 깊은 copy, 내부 객체까지 copy

a[2].append(6)

print(id(a))  # 1991522293064
print(id(b))  # 1991522373384, 겉껍데기 객체는 copy 됨
print(id(c))  # 1991522354632, 동일하게 copy 된 것으로 나타남

print(a)  # 1991522293064, [1, 2, [3, 4, 6], 5]
print(b)  # 1991522373384, [1, 2, [3, 4, 6], 5], 분명 copy 되었으나 내부 객체는 이전 객체를 참조함
print(c)  # 1991522354632, [1, 2, [3, 4], 5]  깊은 복사로 인해 내부 객체도 copy 되어 영향을 받지 않음

"""
Palindrome:
    제약사항: 영문숫자, 대소문자 구분하지 않음.
"""

import re
from collections import deque

def palindrome_deque(string: str) -> bool:
    deq = deque([s.lower() for s in string if s.isalnum()])
    while len(deq) > 1:
        if deq.popleft() != deq.pop():
            return False
    return True


var1 = 'A man, a plan, a canal: Panama'
var2 = 'race a car'
print(palindrome_deque(string=var1))  # True
print(palindrome_deque(string=var2))  # False


def palindrome_slicing(string: str) -> bool:
    string = string.lower()  # 소문자로 통일
    string = re.sub('[^a-z0-9]', '', string)  # 특수문자 필터
    return string == string[::-1]  # 역 슬라이싱!

print(palindrome_slicing(string=var1))  # True
print(palindrome_slicing(string=var2))  # False

["digl 8 1 5 1", "letl art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]

["letl art can", "let3 art zero", "let2 own kit dig", "digl 8 1 5 1", "dig2 3 6"]

def reorder_log_files(logs: list) -> list:
    letters, digits = [], []
    for log in logs:
        if log.split()[1].isdigit():
            digits.append(log)
        else:
            letters.append(log)

    letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
    return letters + digits


logs = ["digl 8 1 5 1", "letl art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]
reorder_log_files(logs=logs)  # ["letl art can", "let3 art zero", "let2 own kit dig", "digl 8 1 5 1", "dig2 3 6"]

import re
import collections
from typing import List


def most_common_word(paragraph: str, banned: List[str]) -> str:
    words = [
        word
        for word in re.sub(r'[^\w]', ' ', paragraph).lower().split()
        if word not in banned
    ]

    # [CASE 1] Using collections.Counter
    counts = collections.Counter(words)
    return counts.most_common(1)[0][0]
    
    # [CASE 2] Using collections.defaultdict
    # counts = collections.defaultdict(int)
    # for word in words:
    #     counts[word] += 1
    # return max(counts, key=counts.get)


paragraph = 'Bob hit a ball, the hit BALL flew far after it was hit.'
banned = ['hit']
print(most_common_word(paragraph=paragraph, banned=banned))  # 'ball'

from collections import defaultdict


def make_anagram(anagrams: defaultdict, word: str) -> dict:
    anagrams[''.join(sorted(word))].append(word)
    return anagrams

words = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
anagrams = defaultdict(list)
for word in words:
    make_anagram(anagrams=anagrams, word=word)

print([sorted(value) for value in anagrams.values()])  # [['ate', 'eat', 'tea'], ['nat', 'tan'], ['bat']]

import re


def get_sub_palindrome(string: str, left: int, right: int) -> str:
    # Expanding from substring length 2 or 3
    while left >= 0 and right < len(string) and string[left] == string[right]:
        left -= 1
        right += 1
    return string[left + 1:right]


def solution(string):
    # 영소문자, 특수문자 제거
    string = string.lower()
    string = re.sub('[^a-z0-9]', '', string)

    # 한 글자이거나, 문자열 전체가 펠린드롬인 경우
    if len(string) < 2 or string == string[::-1]:
        return len(string)

    # 가장 긴 부분 펠린드롬 구하기
    answer = ''
    for i in range(0, len(string) - 1):
        answer = max(
            answer,
            get_sub_palindrome(string, i, i + 1),
            get_sub_palindrome(string, i, i + 2),
            key=len
        )
    return len(answer)

nums, target = [2, 7, 11, 15], 9

[0, 1]

"""
Brute-Force, O(n^2)
"""

def get_two_sum_index_that_match_target1(nums: list, target: int) -> list:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []


nums, target = [2, 7, 11, 15], 9
print(get_two_sum_index_that_match_target1(nums, target))

"""
Use keyword "in", O(n)
"""

def get_two_sum_index_that_match_target2(nums: list, target: int) -> list:
    for idx, num in enumerate(nums):
        complement = target - num
        if complement in nums[idx + 1:]:
            return [idx, nums.index(complement)]
    return []


nums, target = [2, 7, 11, 15], 9
print(get_two_sum_index_that_match_target2(nums, target))

"""
Use reverse dict, advanced O(n)
    -> find the index directly by dict

풀이 3: 첫 번째 수를 뺀 결과 키 조회
    -> 인덱스와 값을 바꿔 값을 key 로 갖는 dict 자료형을 활용합니다.
    -> 첫 번째 수를 뺀 나머지 key 값에 해당하는 value 가 곧 찾는 인덱스가 되도록 합니다.
    -> 나머지 key 값이 주어진 데이터에 없을 수도 있으므로, 조건처리를 잘 해줍니다.
"""

def get_two_sum_index_by_dict(nums: list, target: int) -> list:
    nums_map = {}
    for idx, num in enumerate(nums):
        if target - num in nums_map:
            return [nums_map[target - num], idx]  # find directly using hash key
        nums_map[num] = idx
    return []


nums, target = [2, 7, 11, 15], 9
print(get_two_sum_index_by_dict(nums, target))

"""
Two pointer, optimized O(n)

풀이 4: 투 포인터 활용하기
    -> 양 끝 포인터에서부터 탐색합니다.
    -> 탐색 이전에 정렬이 필요합니다.
    -> 그러나, 정렬하면 인덱스가 흐트러지기 때문에 답을 구할 수 없습니다.

따라서, 인덱스를 구하는 것이 아닌 매칭되는 값을 구하는 문제라면 투 포인터를 활용할 수 있습니다.
"""

def get_two_sum_index_by_dict(nums: list, target: int) -> list:
    nums_map = {}
    for idx, num in enumerate(nums):
        if target - num in nums_map:
            return [nums_map[target - num], idx]  # find directly using hash key
        nums_map[num] = idx
    return []


nums, target = [2, 7, 11, 15], 9
print(get_two_sum_index_by_dict(nums, target))

[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

6

"""
Two pointer

투 포인터를 활용해 양 끝점 중 더 낮은 높이에서 높은 높이로 포인터를 이동시키며 진행합니다. (같은 경우 왼쪽 포인터 진행)
포인터가 이동할 때마다 각 사이드에서의 높이의 차이만큼씩 빗물의 양을 더해 나갑니다.
새로운 위치에서의 높이가 이전 위치에서의 최대 높이보다 높을 경우 최대 높이와 포인터 인덱스를 그것으로 교체합니다.
종료조건은 두 포인터가 만나는 지점입니다.
"""


def trap(height: list) -> int:
    if not height:
        return 0

    result = 0
    start, end = 0, len(height) - 1
    left_max, right_max = height[start], height[end]

    while start < end:
        left_max = max(left_max, height[start])
        right_max = max(right_max, height[end])
        if left_max <= right_max:
            result += left_max - height[start]
            start += 1
        else:
            result += right_max - height[end]
            end -= 1

    return result

nums = [-1, 0, 1, 2, -1, -4]

[
    [-1, 0, 1],
    [-1, -1, 2],
]

from typing import List


def get_three_sum(nums: List[int]) -> List[List[int]]:
    results = []
    nums.sort()
    
    for i in range(len(nums) - 2):  # Two pointer
        # 중복된 값 건너뛰기
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # 간격을 좁혀가며 합 sum 계산
        left, right = i + 1, len(nums) - 1
        while left < right:
            three_sum = nums[i] + nums[left] + nums[right]
            if three_sum < 0:
                left += 1
            elif three_sum > 0:
                right -= 1
            else:
                # 0 인 경우 정답 처리
                results.append([nums[i], nums[left], nums[right]])

                # 다음 항에 동일한 값이 있는 경우 한칸 더 이동
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                # 포인터를 다음 항으로 이동
                left += 1
                right -= 1

    return results


nums = [-1, 0, 1, 2, -1, -4]
print(get_three_sum(nums=nums))

prices = [7, 1, 5, 3, 6, 4]

# 1 일때 사서 6 일때 팔면 최대 수익 5
5

import sys
from typing import List


INF = sys.maxsize


def max_profit(prices: List[int]) -> int:
    profit = 0
    min_price = INF

    # 최저점(min_price)과 최대값(profit)을 계속 갱신
    for price in prices:
        min_price = min(min_price, price)
        profit = max(profit, price - min_price)

    return profit


prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices=prices))

1->2

False

1->2->3->2->1

True

class ListNode:
    def __init__(self, value: int, node: ListNode = None):
        self.value = value
        self.next = node


def is_palindrome(head: ListNode) -> bool:
    if head is None:
        return False

    # rev 는 연결 리스트의 역순. 엄밀히는 slow 포인터의 역순!
    # 따라서 마지막에 rev 와 slow 의 값을 순차적으로 비교하면 됨.
    rev = None

    # 동일 출발점인 head 에서 시작
    slow = fast = head

    # 런너를 이용해 역순 연결 리스트 구성
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next

    # fast 가 None 인지 여부에 따라 중앙값이 있는지 없는지 확인
    # 연결 리스트의 노드가 홀수 개인 경우 중앙값이 존재하게 되므로, slow 포인터의 개수가 rev 보다 하나 많게 됨
    # 따라서 한 칸 진행한 slow.next 부터 rev 와 비교 시작!!
    if fast:
        slow = slow.next

    # rev 와 slow 를 하나씩 탐색하며 팰린드롬 여부 확인
    while rev and rev.value == slow.value:
        slow, rev = slow.next, rev.next
    return not rev


# Test!
nums = [1, 2, 3, 2, 1]
head = ListNode(nums[0])
node = head
for num in nums[1:]:
    next = ListNode(num)
    node.next = next
    node = next

# Palindrome??
print(is_palindrome(head=head))  # True

class Node:
    def __init__(self, item = None, next = None):
        self.item = item
        self.next = next


class Stack:
    def __init__(self):
        self.last = None

    def push(self, item):
        self.last = Node(item, self.last)

    def pop(self):
        item = self.last.item
        self.last = self.last.next
        return item


stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)

for _ in range(5):
    print(stack.pop())  # 5, 4, 3, 2, 1 순으로 출력

from collections import deque


class MyStack:
    def __init__(self):
        """대표적인 큐 구현체인 데크 활용"""
        self.q = deque()

    def push(self, value):
        """스택이므로 마지막에 push 한다는 개념"""
        # Case 1: Use loop
        self.q.append(value)
        for _ in range(len(self.q) - 1):
            """맨 앞에 있던 값이 맨 뒤로 가도록 데크의 길이보다 1 적게 순회"""
            self.q.append(self.q.popleft())

    def advanced_push(self, value):
        # Case 2: Use extend method
        new_q = deque([value])
        new_q.extend(self.q)
        self.q = new_q

    def pop(self):
        """스택이므로 마지막 값을 pop 한다는 개념"""
        return self.q.popleft()

    def top(self):
        """마지막 값을 가져옴"""
        return self.q[0]

    def empty(self):
        """스택이 비었는지 확인"""
        return len(self.q) == 0

"""
[1] 스택 한 개를 활용한 풀이
    -> push 할 때 입력된 값을 스택의 제일 하단으로 보내고
    -> 기존의 스택은 뒤집어서(reversed) 새 스택의 뒤에 연결(extend) 해줍니다.
    -> 말 그대로 reversed 모듈과 extend 메서드를 사용할 수도 있습니다.
"""

class MyQueueOne:
    def __init__(self):
        """오리지날 스택인 list 활용"""
        self.stack = []

    def push(self, value):
        """큐이므로 마지막에 push 한다는 개념"""
        # Case 1: Reverse and append self.stack to new stack
        new_stack = [value]
        self.stack = list(reversed(self.stack))  # 직접 구현 reversed 기능을 사용하도록.
        for _ in range(len(self.stack)):
            new_stack.append(self.stack.pop())
        self.stack = new_stack

    def advanced_push(self, value):
        # Case 2: Extend self.stack to new stack
        new_stack = [value]
        new_stack.extend(self.stack)
        self.stack = new_stack

    def pop(self):
        """큐이므로 첫 번째 값을 pop 한다는 개념"""
        return self.stack.pop()

    def peek(self):
        """첫 번째 값을 가져옴"""
        return self.stack[-1]

    def empty(self):
        """큐가 비었는지 확인"""
        return len(self.stack) == 0

"""
[2] 스택 두 개를 활용한 풀이
    -> 여기서는 reversed 된 출력용 output 스택을 하나 더 씁니다.
    -> output 은 peek 시에 한번 초기화됩니다.
"""

class MyQueueTwo:
    def __init__(self):
        self.input = []
        self.output = []

    def push(self, value):
        self.input.append(value)

    def pop(self):
        self.peek()  # output 한번 초기화!
        return self.output.pop()

    def peek(self):
        """output 이 없으면 모두 재입력 (한번 초기화)"""
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self):
        return len(self.stack) == 0

[
    1->4->5,
    1->3->4,
    2->6
]

1->1->2->3->4->4->5->6

import heapq
from typing import List


class ListNode:
    def __init__(self, value: int, node: ListNode = None):
        self.value = value
        self.next = node


def merge_K_lists(lists: List[ListNode]) -> ListNode:
    root = result = ListNode(None)
    heap = []

    # 각 연결 리스트의 루트를 힙에 저장
    for i in range(len(lists)):
        if lists[i]:
            # (value, index, node) 형태로 heappush 하면 value 우선순위대로 오름차순 정렬됨
            heapq.heappush(heap, (lists[i].value, i, lists[i]))

    # 힙 추출 이후 다음 노드는 다시 저장
    while heap:
        node = heapq.heappop(heap)
        idx = node[1]
        result.next = node[2]

        result = result.next
        if result.next:
            heapq.heappush(heap, (result.next.value, idx, result.next))

    return root.next

from collections import defaultdict


class ListNode:
    def __init__(self, key: int = None, value: int = None):
        self.key = key
        self.value = value
        self.next = None


class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.table = defaultdict(ListNode)

    def put(self, key: int, value: int) -> None:
        index = key % self.size

        # 인덱스에 노드가 없다면 삽입 후 종료
        if self.table[index].value is None:
            self.table[index] = ListNode(key, value)
            return

        # 인덱스에 노드가 존재하는 경우 연결 리스트 처리
        node = self.table[index]
        while node:
            # 같은 키라면 업데이트 후 종료
            if node.key == key:
                node.value = value
                return
            # 마지막 노드까지 오면 break
            if node.next is None:
                break
            node = node.next
        node.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = key % self.size
        if self.table[index].value is None:
            return -1

        # 노드가 존재할 때 일치하는 키 탐색
        node = self.table[index]
        while node:
            # 일치하는 키가 있으면 해당 값 반환
            if node.key == key:
                return node.value
            node = node.next
        return -1

    def remove(self, key: int) -> None:
        index = key % self.size
        if self.table[index].value is None:
            return

        # 인덱스의 첫 번째 노드일 때 삭제 처리
        node = self.table[index]
        if node.key == key:
            self.table[index] = ListNode() if node.next is None else node.next
            return

        # 연결 리스트 노드 삭제
        prev = node
        while node:
            if node.key == key:
                prev.next = node.next
                return
            prev, node = node, node.next


hashMap = MyHashMap()
hashMap.put(1, 1)
hashMap.put(2, 2)
hashMap.get(1)  # return 1
hashMap.get(3)  # return -1
hashMap.put(2, 1)  # update 2's value to 1
hashMap.get(2)  # return 1
hashMap.remove(2)  # remove key 2 node
hashMap.get(2)  # return -1

11110
11010
11000
00000

1

11000
11000
00100
00011

3

from typing import List


def num_is_islands(grid: List[List[str]]) -> int:
    def dfs(i, j):
        # 더 이상 땅이 아닌 경우 종료
        if i < 0 or i >= len(grid) or \
                j < 0 or j >= len(grid[0]) or \
                grid[i][j] != '1':
            return

        # 방문 처리하고 동서남북 탐색
        grid[i][j] = '0'
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                # 재귀로 dfs 를 호출하며 인접한 모든 지점을 탐색 후 방문처리
                # 더 이상 인접한 지점이 없다면 하나의 섬으로 간주하고 count 1 증가
                # 다음 탐색 시에 방문했던 노드를 또 가게 되면 이미 방문처리 되었기 때문에 또 방문하지 않음
                dfs(i, j)
                count += 1

    return count  # 방문한 섬의 개수 반환


grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1'],
]
print(num_is_islands(grid=grid))  # 3

"""
[1] 순열: 직접 구현하기!
"""

from typing import List


def permute(nums: List[int]) -> List[List[int]]:
    results = []
    prev_elems = []

    def dfs(elems):
        # 리프 노드일 때 결과 추가
        if len(elems) == 0:
            results.append(prev_elems[:])  # copy data

        # 순열 생성 재귀 호출
        for e in elems:
            next_elems = elems[:]
            next_elems.remove(e)

            prev_elems.append(e)
            dfs(next_elems)
            prev_elems.pop()

    dfs(nums)
    return results

"""
[2] 순열: itertools 활용하기~
"""

from typing import List
from itertools import permutations


def permute(nums: List[int]) -> List[List[int]]:
    return list(permutations(nums))

n = 4
k = 2

[
    [2, 4],
    [3, 4],
    [2, 3],
    [1, 2],
    [1, 3],
    [1, 4],
]

"""
[1] 조합: 직접 구현하기!
"""

from typing import List


def combine(n: int, k: int) -> List[List[int]]:
    results = []

    def dfs(elems, start: int, k: int):
        if k == 0:
            results.append(elems[:])
            return

        # 자기 자신 이전의 모든 값을 고정하여 재귀 호출
        for i in range(start, n + 1):
            elems.append(i)
            dfs(elems, i + 1, k - 1)
            elems.pop()

    dfs([], 1, k)
    return results

"""
[2] 조합: itertools 활용하기~
"""

from typing import List
from itertools import combinations


def combine(n: int, k: int) -> List[List[int]]:
    return list(combinations(range(1, n + 1), k))

K = 2
N = 4
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]

2

import heapq
from typing import List
from collections import defaultdict


def network_delay_time(times: List[List[int]], N: int, K: int) -> int:
    graph = defaultdict(int)
    # 그래프 인접 리스트 구성
    for u, v, w in times:
        graph[u].append((v, w))

    # 큐 변수: [(소요시간, 정점)]
    queue = [(0, K)]
    dist = defaultdict(int)

    # 우선순위 큐 최소값 기준으로 정점까지 최단 경로 삽입
    while queue:
        time, node = heapq.heappop(queue)
        if node not in dist:
            for v, w in graph[node]:
                alt = time + w
                heapq.heappush(queue, (alt, v))
    
    # 모든 노드의 최단 경로 존재 여부 판별
    if len(dist) == N:
        return max(dist.values())
    return -1

class BinaryHeap(object):
    def __init__(self):
        self.items = [None]

    def __len__(self):
        # except index 0
        return len(self.items) - 1

    # 삽입 시 실행, 반복 구조 구현
    def _percolate_up(self):
        i = len(self)
        parent = i // 2  # 이진 트리 레벨에 따라 부모 탐색
        while parent > 0:
            if self.items[i] < self.items[parent]:
                self.items[parent], self.items[i] = self.items[i], self.items[parent]
            i = parent
            parent = i // 2

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    # 추출시 실행, 재귀 구조 구현
    def _percolate_down(self, idx):
        left = idx * 2
        right = idx * 2 + 1
        smallest = idx

        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left

        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right

        if smallest != idx:
            self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx]
            self._percolate_down(smallest)

    def extract(self):
        extracted = self.items[1]
        self.items[1] = self.items[len(self)]
        self.items.pop()
        self._percolate_down(1)
        return extracted

def bubble_sort(A):
    for i in range(1, len(A)):
        for j in range(0, len(A) - 1):
            cnt = 0
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]
                cnt += 1
            if cnt > 0:
                return

nums = [1, 2, -1, -3, 5, 3, 6, 7]
k = 3

[3, 3, 5, 5, 6, 7]

"""
슬라이딩 윈도우 1: 브루트 포스로 풀기
"""

from typing import List


def max_sliding_window1(nums: List[int], k: int) -> List[int]:
    if not nums:
        return nums

    r = []
    for i in range(len(nums) - k + 1):
        r.append(max(nums[i:i + k]))

    return r

"""
슬라이딩 윈도우 2: 큐 활용하기
"""

from typing import List


def max_sliding_window2(nums: List[int], k: int) -> List[int]:
    pass

def edit_distance(str1, str2, insert, delete, change):
    n, m = len(str1), len(str2)

    # Make memoization
    answer = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # Initialize
    for i in range(1, n + 1):
        answer[1][0] = i
    for j in range(1, m + 1):
        answer[0][j] = j

    # Calc distance
    for i in range(n):
        for j in range(m):
            answer[i + 1][j + 1] = min(
                answer[i][j + 1] + delete,
                answer[i + 1][j] + insert,
                answer[i][j] + (0 if str1[i] == str2[j] else change),
            )

    return answer[n][m]

> n = 5
> arr1 = [9, 20, 28, 18, 11]
> arr2 = [30, 1, 21, 17, 28]
["#####", "# # #", "### #", "#  ##", "#####"]

"""
비밀 지도:
    이차원 배열로 이루어진 지도1, 지도2를 겹쳐서 전체 지도를 얻는 문제
    지도는 한 변의 길이가 n 인 정사각형
    주어진 두 정수 배열의 각 숫자를 이진수로 변환하면 이차원 배열의 행이 됨
    1은 벽("#"), 0은 공백(" ")
"""

from typing import List


def secret_map(n: int, arr1: List[int], arr2: List[int]) -> List[str]:
    answer = []

    arr1 = [f'{int(num):b}'.zfill(n) for num in arr1]
    arr2 = [f'{int(num):b}'.zfill(n) for num in arr2]

    for row in range(n):
        answer.append(''.join([
            str(
                int(arr1[row][idx]) or int(arr2[row][idx])
            ).replace('0', ' ').replace('1', '#')
            for idx in range(n)
        ]))

    return answer

"1S2D*3T"
"1D2S#10S"

37  # 1^1 * 2 + 2^2 * 2 + 3^3
9  # 1^2 + 2^1 * (-1) + 10^1

def dart(dart_result: str) -> int
    nums = [0]

    for s in dart_result:
        if s == 'S':
            nums[-1] **= 1
            nums.append(0)
        elif s == 'D':
            nums[-1] **= 2
            nums.append(0)
        elif s == 'T':
            nums[-1] **= 3
            nums.append(0)
        elif s == '*':
            # 이전 값, 그 이전 값 모두 두 배 처리
            nums[-2] *= 2
            if len(nums) > 2:
                nums[-3] *= 2
        elif s == '#':
            nums[-2] *= -1
        else:
            # 자릿수 올림
            nums[-1] = nums[-1] * 10 + int(s)

    return sum(nums)

m = 4
n = 5
board = ["CCBDE", "AAADE", "AAABF", "CCBBF"]

14

from typing import List


def friends_4_block(m: int, n: int, board: List[str]) -> int:
    board = [list(x) for x in board]

    matched = True
    while matched:
        # 1) 일치 여부 판별
        matched = []
        for i in range(m - 1):
            for j in range(n - 1):
                if board[i][j] == board[i][j + 1] == board[i + 1][j] == board[i + 1][j + 1] != '#':
                    matched.append([i, j])

        # 2) 일치한 위치 삭제
        for i, j in matched:
            board[i][j] = board[i][j + 1] = board[i + 1][j] = board[i + 1][j + 1] = '#'

        # 3) 빈공간 블럭 처리
        for _ in range(m):
            for i in range(m - 1):
                for j in range(n):
                    if board[i + 1][j] == '#':
                        board[i + 1][j], board[i][j] = board[i][j], '#'

    return sum(x.count('#') for x in board)                

["2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"]

1