끼룽의 블로그

# swea 1226 '미로'

from collections import deque

T = 10

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

for t in range(1, T+1):
    input()
    MAP = []
    N = 16
    for _ in range(N):
        MAP.append(list(map(int, input())))

    for i in range(N):
        for j in range(N):
            if MAP[i][j] == 2:
                st_i, st_j = i, j
            if MAP[i][j] == 3:
                fn_i, fn_j = i, j

    queue = deque()
    queue.append((st_i, st_j))
    MAP[st_i][st_j] = 1

    flag = 0
    while queue:
        i, j = queue.popleft()
        if MAP[i][j] == 3:
            flag = 1
            break

        MAP[i][j] = 1

        for d in range(4):
            next_i = i + di[d]
            next_j = j + dj[d]

            if MAP[next_i][next_j] == 1:
                continue

            queue.append((next_i, next_j))

    print('#{} {}'.format(t, flag))

# swea 1224 '게산기3'

def postfix_notation(string):
    global op_rank

    result = ''
    stk = []
    for c in string:
        if c.isdigit():
            result += c
            continue

        if len(stk) == 0 or c == '(':
            stk.append(c)
            continue

        if c == ')':
            while stk[-1] != '(':
                result += stk.pop()
            stk.pop()
            continue

        while len(stk) and op_rank[stk[-1]] >= op_rank[c]:
            result += stk.pop()

        stk.append(c)

    while len(stk):
        result += stk.pop()

    return result


def calculate(string):
    stk = []

    for c in string:
        if c.isdigit():
            stk.append(int(c))
            continue

        num2 = stk.pop()
        num1 = stk.pop()

        result = 0
        if c == '+':
            result = num1 + num2
        else:
            result = num1 * num2

        stk.append(result)

    return stk.pop()


if __name__ == '__main__':
    op_rank = {
        '(': 0,
        '+': 1,
        '*': 2
    }

    T = 10

    for t in range(1, T+1):
        N = int(input())
        string = input().rstrip()
        result = calculate(postfix_notation(string))

        print('#{} {}'.format(t, result))

# swea 1223 '계산기2'(전용)

def parse_notation(string):
    op_rank = {
        '+': 1,
        '*': 2
    }

    result = ''
    stk = []
    for c in string:
        if c.isdigit():
            result += c
            continue

        if len(stk) == 0:
            stk.append(c)
            continue

        while len(stk) and op_rank[stk[-1]] >= op_rank[c]:
            result += stk.pop()

        stk.append(c)

    while len(stk):
        result += stk.pop()

    return result


def calculate(string):
    stk = []
    for c in string:
        if c.isdigit():
            stk.append(int(c))
            continue

        num1 = stk.pop()
        num2 = stk.pop()
        if c == '+':
            stk.append(num1 + num2)
        else:
            stk.append(num1 * num2)

    return stk.pop()


if __name__ == '__main__':
    T = 10

    for t in range(1, T+1):
        length = int(input())
        string = input()
        parsed_string = parse_notation(string)
        result = calculate(parsed_string)

        print('#{} {}'.format(t, result))

# swea 1219 '길찾기'

def check_way(edges, visits, node):
    if node == 99:
        return 1

    for next_node in edges[node]:
        if visits[next_node]:
            continue

        visits[next_node] = True
        if check_way(edges, visits, next_node):
            return 1

    return 0


if __name__ == '__main__':
    T = 10

    for _ in range(1, T+1):
        t, n = map(int, input().split())

        edges = [list() for _ in range(100)]
        visits = [False for _ in range(100)]

        input_list = list(map(int, input().split()))
        for i in range(n):
            v1 = input_list[2 * i]
            v2 = input_list[2 * i + 1]

            edges[v1].append(v2)

        visits[0] = True
        result = check_way(edges, visits, 0)

        print('#{} {}'.format(t, result))

# swea 1234 '비밀번호'

T = 10

for t in range(1, T+1):
    n, password = input().split()
    n = int(n)

    stk = []

    for c in password:
        if stk and c == stk[-1]:
            stk.pop()
        else:
            stk.append(c)

    result = ''.join(stk)

    print('#{} {}'.format(t, result))

# swea 2005 '파스칼의 삼각형'

T = int(input())

for t in range(1, T+1):
    N = int(input())
    dp = [[], [0, 1, 0]]
    for i in range(2, N + 1):
        dp.append([0])
        for j in range(1, i + 1):
            dp[i].append(dp[i - 1][j - 1] + dp[i - 1][j])
        dp[i].append(0)

    print('#{}'.format(t))
    for i in range(1, N + 1):
        print(*dp[i][1:-1], sep=' ')

# swea 1216 '회문2'

T = 10
for t in range(1, T+1):
    t = int(input())
    MAP = []
    for _ in range(100):
        MAP.append(list(input()))

    max_length = 0
    for length in range(100, 0, -1):
        for i in range(100 - length + 1):
            for j in range(100 - length + 1):
                j_offset = 0
                j_flag = True
                while j_offset < length // 2:
                    if MAP[i][j + j_offset] != MAP[i][j + length - 1 - j_offset]:
                        j_flag = False
                        break
                    j_offset += 1

                if j_flag:
                    max_length = length
                    break

                i_offset = 0
                i_flag = True
                while i_offset < length // 2:
                    if MAP[i + i_offset][j] != MAP[i + length - 1 - i_offset][j]:
                        i_flag = False
                        break
                    i_offset += 1

                if i_flag:
                    max_length = length
                    break
            if max_length:
                break
        if max_length:
            break

    print('#{} {}'.format(t, max_length))

# swea 3143 '가장 빠른 문자열 타이핑'

T = int(input())

for t in range(1, T+1):
    A, B = input().strip().split()

    jump_dict = {}
    for i in range(1, len(B)):
        if B[-1 - i] in jump_dict:
            continue
        jump_dict[B[-1 - i]] = i

    cnt = 0
    i = len(B) - 1
    k = 0

    while i < len(A):
        if k == len(B):
            jump = len(B)
            cnt += 1
            i += jump
            k = 0
            continue

        if A[i - k] == B[-1 - k]:
            k += 1
        else:
            jump = jump_dict.get(A[i], len(B))
            i += jump
            k = 0

    result = len(A) - cnt * (len(B) - 1)

    print('#{} {}'.format(t, result))