1. 가능한 가지 수 세기
def solution1(array):
n = len(test1) # 행 개수
m = len(test1[0]) # 열 개수
result = []
# 열 기준
for j in range(m):
temp = 0
for i in range(n):
if test1[i][j] == 1 and test1[i-1][j] == 0:
temp += 1
break
elif test1[i][j] == 1 and test1[i+1][j] != 0:
temp += 1
break
elif test1[i][j] == 2 and i == (n - 1): # 0과 2로 구성된 열에서 마지막 행의 2일 경우 : 아예 히스토그램이 없을 경우를 추가
temp += 2
elif test1[i][j] == 2 and test1[i+1][j] != 0:
temp += 1
result.append(temp)
answer = 1
for num in result:
answer *= num
return answer
### 입력 예시 ###
test1 = [[0,0,0,0,0],
[0,0,0,0,0],
[2,2,0,0,0],
[1,0,1,0,0],
[2,1,2,2,2],
[2,1,2,2,2]]
print(solution1(test1))
Python
복사
2.
from collections import Counter
def solution(grid, t):
N = len(grid)
# Check if a k x k grid meets the condition
def can_form_square(k):
for i in range(0, N, k):
for j in range(0, N, k):
# Collect all characters in the current k x k square
char_count = Counter()
for x in range(i, i + k):
for y in range(j, j + k):
char_count[grid[x][y]] += 1
# If the unique character count exceeds t, return False
if len(char_count.keys()) > t:
return False
return True
# Find all possible values of k (N's divisors excluding N itself)
divisors = [k for k in range(1, N) if N % k == 0]
# Check each k from largest to smallest
for k in sorted(divisors, reverse=True):
if can_form_square(k):
return k # Return the largest valid k
return 1 # If no valid k found, the minimum is always 1
#### 입력 예시 ####
grid = [
"baabcc",
"bbbbcc",
"ababbb",
"bbbacc",
"ccbcac",
"bcccca"
]
t = 2
print(solution(grid, t))
Python
복사
3. 지뢰 찾기
•
BFS 알고리즘
•
큐 자료구조 : collections.deque
Python
복사