743. 네트워크 지연 시간
너비 우선 탐색(BFS)을 사용하여 현재 노드 k에서 시작하여 k와 연결된 모든 노드를 탐색합니다. 만약 노드 to의 시간을 업데이트할 수 있다면, 노드 to를 큐에 추가하여 나중에 고려합니다.
def calculateNetworkDelay(networkConnections, nodeCount, startNode):
"""
:type networkConnections: List[List[int]]
:type nodeCount: int
:type startNode: int
:rtype: int
"""
from collections import defaultdict
time_cost = {}
adjacency_list = defaultdict(list)
# Initialize all nodes with infinite time cost
for i in range(1, nodeCount + 1):
time_cost[i] = float('inf')
# Set the start node cost to 0
time_cost[startNode] = 0
# Build the adjacency list
for source, destination, time in networkConnections:
adjacency_list[source].append((destination, time))
# Use a queue for BFS
queue = [startNode]
while queue:
current_node = queue.pop(0)
for neighbor, travel_time in adjacency_list[current_node]:
if time_cost[current_node] + travel_time < time_cost[neighbor]:
queue.append(neighbor)
time_cost[neighbor] = time_cost[current_node] + travel_time
# Find the maximum time cost
max_time = max(time_cost.values())
if max_time == float('inf'):
return -1
return max_time
3206. 교대 그룹 I
각 위치 i를 순회하며 i-1과 i+1 위치의 값이 현재 위치와 다른지 확인합니다.
def countAlternatingGroups(colorArray):
"""
:type colorArray: List[int]
:rtype: int
"""
length = len(colorArray)
count = 0
for i in range(length):
# Check if current color is different from both neighbors
if colorArray[i] != colorArray[(i + 1) % length] and colorArray[i] != colorArray[(i - 1) % length]:
count += 1
return count
3208. 교대 그룹 II
원래 배열 뒤에 k-1 길이의 배열을 추가합니다. 시작점 l을 정하고, 오른쪽 위치 r을 계속 오른쪽으로 이동시키며 colors[r] != colors[r-1]인지 확인합니다. 가능한 한 긴 교대 구간 [l, r-1]을 찾습니다. 만약 구간 내 요소 수가 k개 이상이라면, (r-1-l+1)-k+1개의 교대 그룹을 얻을 수 있습니다. 다음 시작점 l=r에서 재탐색을 시작합니다.
def countAlternatingGroupsExtended(colorArray, groupSize):
"""
:type colorArray: List[int]
:type groupSize: int
:rtype: int
"""
length = len(colorArray)
# Extend the array with the first k-1 elements
extendedColors = colorArray + colorArray[:groupSize - 1]
result = 0
left = 0
right = 1
while left < length:
while right < length + groupSize - 1 and extendedColors[right] != extendedColors[right - 1]:
right += 1
# If we found a long enough alternating sequence
if right - left >= groupSize:
result += right - left - groupSize + 1
# Move to the next possible starting position
left = right
right += 1
return result
3250. 단조 배열 쌍의 수 I
동적 프로그래밍(DP)을 사용합니다. dp[i][j]를 arr1[i]=j일 때, i+1개의 요소로 구성된 단조 배열의 수로 정의합니다. dp[i][v2] = sum(dp[i-1][v1])이며, v2 >= v1이고 nums[i-1]-v1 >= nums[i]-v2 >= 0를 만족해야 합니다. v2 >= nums[i]-nums[i-1]+v1이므로, v2 >= v1+d (d = max(0, nums[i]-nums[i-1])). 상태 전환은 dp[i][j] = dp[i][j-1] + dp[i-1][j-d]로 표현됩니다.
def countMonotonicPairs(numberSequence):
"""
:type numberSequence: List[int]
:rtype: int
"""
MOD = 10**9 + 7
n, max_val = len(numberSequence), max(numberSequence)
# Initialize DP table
dp = [[0] * (max_val + 1) for _ in range(n)]
# Base case: first element
for value in range(numberSequence[0] + 1):
dp[0][value] = 1
# Fill DP table
for i in range(1, n):
diff = max(0, numberSequence[i] - numberSequence[i - 1])
for j in range(diff, numberSequence[i] + 1):
if j == 0:
dp[i][j] = dp[i - 1][j - diff]
else:
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - diff]) % MOD
# Sum up the last row
return sum(dp[n - 1]) % MOD
3251. 단조 배열 쌍의 수 II
I 문제와 동일한 접근 방식을 사용하지만, 더 큰 입력을 처리할 수 있도록 최적화합니다.
def countMonotonicPairsOptimized(numberSequence):
"""
:type numberSequence: List[int]
:rtype: int
"""
MOD = 10**9 + 7
n, max_val = len(numberSequence), max(numberSequence)
# Initialize DP table with prefix sums for optimization
dp = [[0] * (max_val + 1) for _ in range(n)]
prefix_sums = [[0] * (max_val + 2) for _ in range(n)]
# Base case: first element
for value in range(numberSequence[0] + 1):
dp[0][value] = 1
# Compute prefix sums for the first row
for j in range(1, max_val + 1):
prefix_sums[0][j] = (prefix_sums[0][j - 1] + dp[0][j]) % MOD
# Fill DP table with optimized prefix sums
for i in range(1, n):
diff = max(0, numberSequence[i] - numberSequence[i - 1])
for j in range(diff, numberSequence[i] + 1):
if j == diff:
dp[i][j] = prefix_sums[i - 1][j - diff] if (j - diff) >= 0 else 0
else:
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - diff]) % MOD
# Update prefix sums for current row
for j in range(1, max_val + 1):
prefix_sums[i][j] = (prefix_sums[i][j - 1] + dp[i][j]) % MOD
# Sum up the last row
return prefix_sums[n - 1][max_val] % MOD
3232. 숫자 게임에서 이길 수 있는지 판단
일의 자리 숫자와 두 자리 숫자의 합이 같지 않은 한, Alice는 반드시 승리합니다.
def canWinNumberGame(numbers):
"""
:type numbers: List[int]
:rtype: bool
"""
total_sum = sum(numbers)
single_digit_sum = 0
for num in numbers:
if num < 10: # Single digit number
single_digit_sum += num
# If the sum of single digit numbers is half of total sum, Alice loses
return False if 2 * single_digit_sum == total_sum else True
51. N-퀸
- 각 층의 위치를 순회하며 가능한 위치를 찾습니다.
- 특정 위치를 결정한 후, 나중에 채울 수 없는 위치를 표시합니다.
- 세 개의 집합을 사용하여 기존 퀸의 위치를 기록합니다: 열, 왼쪽에서 오른쪽으로의 대각선, 오른쪽에서 왼쪽으로의 대각선.
- 현재 위치에 퀸을 배치할 수 있다면, 세 개의 값을 집합에 추가하고 현재 x 층의 열 위치 y를 기록합니다.
- 다음 층 x+1을 확인합니다. 마지막 층에 도달했다면 현재 상황을 저장합니다. 그렇지 않으면 방금 전의 상태를 지우고 다음 위치를 확인합니다.
def solveNQueensProblem(n):
"""
:type n: int
:rtype: List[List[str]]
"""
import copy
solutions = []
board = [["."] * n for _ in range(n)]
def backtrack(row, current_board):
for col in range(n):
# Check if current position is valid
if current_board[row][col] == ".":
# Create a copy of the current board
temp_board = copy.deepcopy(current_board)
# Mark attacked positions
for j in range(col + 1, n):
temp_board[row][j] = "x"
for i in range(row + 1, n):
temp_board[i][col] = "x"
if col + i - row < n:
temp_board[i][col + i - row] = "x"
if col - (i - row) >= 0:
temp_board[i][col - (i - row)] = "x"
# Place the queen
temp_board[row][col] = "Q"
# If we've placed queens in all rows, add to solutions
if row == n - 1:
solutions.append(temp_board)
else:
backtrack(row + 1, temp_board)
backtrack(0, board)
# Format the solutions
formatted_solutions = []
for solution in solutions:
formatted_solution = []
for line in solution:
row_string = ""
for cell in line:
if cell == 'Q':
row_string += 'Q'
else:
row_string += '.'
formatted_solution.append(row_string)
formatted_solutions.append(formatted_solution)
return formatted_solutions
def solveNQueensOptimized(n):
"""
:type n: int
:rtype: List[List[str]]
"""
# Three sets to track occupied columns and diagonals
columns = set()
left_diagonals = set() # x + y
right_diagonals = set() # x - y
solutions = []
current_positions = []
def backtrack(row):
for col in range(n):
# Check if current position is valid
if (col not in columns and
(row + col) not in left_diagonals and
(row - col) not in right_diagonals):
# Place the queen
columns.add(col)
left_diagonals.add(row + col)
right_diagonals.add(row - col)
current_positions.append(col)
# If we've placed queens in all rows, save the solution
if row + 1 == n:
solutions.append(current_positions[:])
else:
backtrack(row + 1)
# Backtrack
columns.remove(col)
left_diagonals.remove(row + col)
right_diagonals.remove(row - col)
current_positions.pop()
backtrack(0)
# Format the solutions
formatted_solutions = []
for positions in solutions:
formatted_solution = []
for i in range(n):
row = ['.'] * n
row[positions[i]] = 'Q'
formatted_solution.append(''.join(row))
formatted_solutions.append(formatted_solution)
return formatted_solutions