짱우로그

전화번호 목록 📝문제 👨‍💻코드 def solution(phone_book): answer = True phone_book.sort() for i in range(len(phone_book) - 1): if phone_book[i] in phone_book[i + 1][:len(phone_book[i])]: answer = False break return answer🤔Review 너무 간단한 문제라고 생각하고 풀었는데 13번 테스트 케이스에서 계속 실패가 나와서 원인을 분석해보니 겹치는게 중간과 끝에 있어도 false로 반환하는게 문제였다. 그래서 접두어로 비교할 수의 크기까지만 비교하고 같아야 접두어로 했더니 테스트케이스 전부 통과되었다.

가장 큰 수 📝문제 👨‍💻코드 def solution(numbers): numbers = list(map(str, numbers)) numbers.sort(key = lambda x: x * 3, reverse = True) return str(int(''.join(numbers))) 🤔Review numbers의 원소 값들을 비교해야 하는데 어떻게 비교할지 방법을 한참 고민했다. str로 비교하는 방법을 찾았고 원소가 1000이하의 수 이기 때문에 각 원소를 str로 변환한 후 *3를 하여 자리수를 맞추고 정렬하여 풀었다.

타겟 넘버 📝문제 👨‍💻코드 from collections import deque def solution(numbers, target): answer = 0 queue = deque() queue.append([numbers[0], 0]) queue.append([-1 * numbers[0], 0]) while queue: sum, idx = queue.popleft() idx += 1 if idx == len(numbers): if sum == target: answer += 1 else: queue.append([sum + numbers[idx], idx]) queue.append([sum - numbers[idx], idx]) return answer 🤔Review 탐색 문제로 처음엔 DFS로 풀려..

11727 - 2xn 타일링 2 📝문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 👨‍💻코드 n = int(input()) dp = [0] * 1001 dp[1] = 1 dp[2] = 3 dp[3] = 5 for i in range(4, n + 1): dp[i] = (dp[i - 2] * 2) + dp[i - 1] print(dp[n] % 10007) 🤔Review 기본적인 타일문제로 점화식을 금방 세워 풀 수 있었다.

1965 - 상자넣기 📝문제 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다. 상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오. 👨‍💻코드 ..

2133 - 타일 채우기 📝문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 👨‍💻코드 n = int(input()) dp = [0] * 31 dp[2] = 3 for i in range(4, 31, 2): dp[i] = (dp[i - 2] * 3) + 2 for j in range(2, i - 2, 2): dp[i] += (dp[j] * 2) print(dp[n]) 🤔Review 타일 문제는 가장 대표적인 dp문제라 쉽게 풀 수 있었다. 하지만 기존에 있던 값들을 *2 해서 다 더해주지 않아 처음엔 틀렸다...

11055 - 가장 큰 증가 부분 수열 📝문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 👨‍💻코드 n = int(input()) arr = list(map(int, input().split())) dp = [] for i in arr: dp.append(i) for i in range(n): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i], dp[j] + arr[..

1748 - 수 이어 쓰기 📝문제 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. 1234567891011121314151617181920212223... 이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오. 👨‍💻코드 n = int(input()) nCount = list(str(n)) ans = 0 if len(nCount) > 1: for i in range(0, len(nCount) - 1): ans += 9 * (10 ** i) * (i + 1) last = n - ((10 ** ((len(nCount)) - 1)) - 1) ans += last * (len(nCount)) print(ans) else: for i in ..

10844 - 포도주 시식 📝문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 👨‍💻코드 n = int(input()) dp = [[0 for _ in range(10)] for _ in range(101)] dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, n + 1): for j in range(10): if j == 0: dp[i][j] = dp[i - 1][j + 1] elif j == 9: dp[i]..

2156 - 포도주 시식 📝문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램..