2개 이하로 다른 비트 (월간 코드 챌린지 시즌2)
-
양의 정수
x에 대한 함수f(x)를 다음과 같이 정의합니다.
-x보다 크고x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
예를 들어,
-f(2) = 3입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
수 비트 다른 비트의 개수
2 000...0010
3 000...0011 1
f(7) = 11입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
수 비트 다른 비트의 개수
7 000...0111
8 000...1000 4
9 000...1001 3
10 000...1010 3
11 000...1011 2
정수들이 담긴 배열numbers가 매개변수로 주어집니다.numbers의 모든 수들에 대하여 각 수의f값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.- 제한사항
- 1 ≤
numbers의 길이 ≤ 100,000 - 0 ≤
numbers의 모든 수 ≤ 10^15
- 1 ≤
- 제한사항
제출한 코드 :
def solution(numbers):
result = []
for x in numbers:
if x % 2 == 0:
result.append(x + 1)
else:
# x의 가장 낮은 0 비트를 1로 바꾸고, 그 다음 비트를 0으로 바꾼다.
bit = 1
while x & bit:
bit <<= 1
result.append(x + bit - (bit >> 1))
return result다리를 지나는 트럭 (스택/큐)
-
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭
0 [] [] [7,4,5,6]
1~2 [] [7] [4,5,6]
3 [7] [4] [5,6]
4 [7] [4,5] [6]
5 [7,4] [5] [6]
6~7 [7,4,5] [6] []
8 [7,4,5,6] [] []
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.- 제한사항
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
- 제한사항
제출한 코드 :
from collections import deque
def solution(bridge_length, weight, truck_weights):
time = 0
bridge_queue = deque([0] * bridge_length) # 다리 길이만큼의 큐 생성
bridge_weight = 0 # 현재 다리 위 트럭들의 총 무게
for truck in truck_weights:
while True:
time += 1
bridge_weight -= bridge_queue.popleft() # 다리에서 트럭이 나가는 경우 무게 감소
if bridge_weight + truck <= weight: # 새로운 트럭이 올라올 수 있는지 확인
bridge_queue.append(truck)
bridge_weight += truck
break
else:
bridge_queue.append(0) # 트럭이 올라올 수 없으면 0을 추가하여 다리 상태 유지
# 마지막 트럭이 다리 위에 올라간 후 다리 길이만큼 시간이 더 필요
time += bridge_length
return time가장 큰 수 (정렬)
- 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
- 제한사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
- 제한사항
제출한 코드 :
from functools import cmp_to_key
def compare(x, y):
if x + y > y + x:
return -1
elif x + y < y + x:
return 1
else:
return 0
def solution(numbers):
# numbers를 문자열로 변환
numbers = list(map(str, numbers))
# 커스텀 정렬 기준으로 정렬
numbers.sort(key=cmp_to_key(compare))
# 정렬된 숫자들을 이어붙임
answer = ''.join(numbers)
# 앞자리 0 처리 (e.g., [0, 0]인 경우 '00' -> '0')
return answer if answer[0] != '0' else '0'소수 찾기 (완전탐색)
- 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
- 제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
- 제한사항
제출한 코드 :
from itertools import permutations
# 소수 판별 함수
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0:
return False
return True
def solution(numbers):
# 모든 숫자 조합을 생성
num_set = set()
for i in range(1, len(numbers) + 1):
perms = permutations(numbers, i)
for perm in perms:
num = int(''.join(perm))
num_set.add(num)
# 소수 판별 후 카운트
prime_count = 0
for num in num_set:
if is_prime(num):
prime_count += 1
return prime_count쿼드압축 후 개수 세기 (월간 코드 챌린지 시즌1)
-
0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
- 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
- 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
- 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
- 제한사항
- arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
- arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
- arr의 각 행에 있는 모든 값은 0 또는 1 입니다.
- arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
제출한 코드 :
def solution(arr):
def compress(x, y, size):
initial = arr[x][y]
all_same = True
for i in range(x, x + size):
for j in range(y, y + size):
if arr[i][j] != initial:
all_same = False
break
if not all_same:
break
if all_same:
if initial == 0:
result[0] += 1
else:
result[1] += 1
else:
new_size = size // 2
compress(x, y, new_size)
compress(x, y + new_size, new_size)
compress(x + new_size, y, new_size)
compress(x + new_size, y + new_size, new_size)
n = len(arr)
result = [0, 0]
compress(0, 0, n)
return result