3월 2주차 코딩테스트

목차

1. 이어 붙인 문자열
2. 카지노 교환원

1. 이어 붙인 문자열

풀이

def solution(s, words):
    result = False

    def dfs(s):
        nonlocal result

        if s == '':
            result = True
            return
        
        for w in words:
            if s.startswith(w):
                dfs(s[len(w):])
    dfs(s)
    return result

Testcase

# 테스트 1
입력값 〉 "zerobase", ["zer", "ro", "ze", "base"]
기댓값 〉 true

2. 카지노 교환원

풀이

def solution(money, chips):
    dp = [float('inf') for _ in range(money + 1)]
    dp[0] = 0

    for i in range(1, money+1):
        for j in range(len(chips)):
            if i - chips[j] >= 0:
                dp[i] = min(dp[i], dp[i - chips[j]] + 1)
    
    return dp[money]

Test case

 #테스트 1
입력값 〉 3000, [1100, 500, 200, 150, 25]
기댓값 〉 5

# 테스트 2
입력값 〉 5000, [1400, 1200, 80, 45, 22, 10]
기댓값 〉 4

3. 반전 스위치

풀이

def solution(status):
    visited = set()
    visited.add(tuple(status))

    all_one = tuple([1 for _ in range(len(status))])

    queue = [(0, status)]
    while queue:
        count, stat =  queue.pop(0)
        for new_stat in get_adj(stat):
            new_stat_tup = tuple(new_stat)
            
            if new_stat_tup in visited:
                continue

            if new_stat_tup == all_one:
                return count + 1
            
            visited.add(new_stat_tup)
            queue.append((count + 1, new_stat))
    
    return -1

def get_adj(s):
    ret = []

    def inv(s):
        t = [0 if i == 1 else 1 for i in s]
        return t
    
    for i in range(len(s)):
        if i == 0:
            ret += [inv(s[i:i+2]) + s[i+2:]]
        elif i == len(s) - 1:
            ret += [s[:i-1] + inv(s[i-1:])]
        else:
            ret += [s[:i-1] + inv(s[i-1:i+2]) + s[i+2:]]
    return ret

Test case

# 테스트 1
입력값 〉 [1, 1, 0, 1, 0, 1]
기댓값 〉 3
# 테스트 2
입력값 〉 [1, 0, 1, 0, 1, 0, 1, 0, 1, 1]
기댓값 〉 5

4. 죽음의 게임

풀이

from math import perm

def solution(n, m):
    max_div = m // 2 + 1

    answer = 0
    for div in range(1, max_div):
        q, r = divmod(m, div)
        if (r == 0) and (q <= n):
            answer += perm(n-1, q-1)
    
    return answer % 100007

Testcase

# 테스트 1
입력값 〉 4, 3
기댓값 〉 6

# 테스트 2
입력값 〉 6, 10
기댓값 〉 125

5. 2회 윷놀이 최강자전

풀이

def solution(N, edges):
    dp = [float('inf') for _ in range(N+1)]
    dp[0] = 0

    first_moves = [0, 4, 5]
    second_moves1 = [1, 2, 3]
    second_moves2 = [1, 2, 3, 4, 5]
    for i in range(N):
        shortcuts = list(map(lambda e: e[1] - 1,
         filter(lambda e: e[0] == i, edges)))
        for start in [i] + shortcuts:
            for move1 in first_moves:
                j = start + move1
                if move1 > 0:
                    shortcuts2 = list(map(lambda e: e[1] - 1, 
                        filter(lambda e: e[0] == j, edges)))
                else:
                    shortcuts2 = []
                for start2 in [j] + shortcuts2:
                    second_moves = second_moves1 if move1 == 0 else second_moves2
                    for move2 in second_moves:
                        k = start2 + move2
                        if k <= N:
                            dp[k] = min(dp[k], dp[i] + 1)
    return dp[N]

Test case

# 테스트 1
입력값 〉 34, [[1, 4], [6, 12], [15, 24]]
기댓값 〉 3

# 테스트 2
입력값 〉 100, [[12, 40], [18, 53], [59, 89]]
기댓값 〉5

출처

해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.

모든 자료는 저작권법에 의하여 보호받는 저작물로서 이에 대한 무단 복제 및 배포를 원칙적으로 금합니다.