3일차부터 23일차는 어디갔냐구요? 아무도 기다리시는 분은 없겠지만 언젠가 업로드하겠습니다.ㅋㅋ
18111번 마인크래프트 땅 고르게 하기
3시간 걸린듯… 그래도 풀어서 행복해ㅎㅎ 처음엔 for문으로 모든 블락을 500x500 을 계속 돌면서 time을 계산함. 그러니까 250,000 즉 포문만 4번 돌아도 10^6으로 1초 안에 못어서 시간 초과 계속 남. 그리고 실제로 돌려보니까 답도 아님ㄷㄷ
bfs, bfs는 절대 아닌 것 같으니까 남은 건 dp 풀이 하나 뿐이라 dp로 접근. dp[i] = i 높이일 때 시간, got - 부족한 블록수 dp[0] = 250,000(한번 돌면서 시간 구하기), got + 넘치는 블록수, 부족한 블록수, 남은 블록수 dp[1] = dp[0] + 부족할 블록수 - 2* 넘치는 블록수 dp[2] = dp[1] + 근데 부족한지 넘치는지 개수를 어떻게 알지 고민하다보니까!!!!!!!!!!!!! 아 잠만 이거 counter 하면되네? 64개가 11개고 63이 1개다만 알면… 대박ㅎㅎ 하면서 바로 성공
import sys
n, m, got = map(int, input().split())
li = []
max = 256
count = {i : 0 for i in range(max + 1)}
result = [[0, got, 0] for _ in range(max + 1)]
# x[0] : times, x[1] : blocks, x[2] : height
for _ in range(n):
li.append(list(map(int, sys.stdin.readline().split())))
for num in li[-1]:
count[num] += 1
for height in range(max + 1):
result[height][2] = height
for num, cnt in count.items():
if num > height:
result[height][0] += ((num - height) * 2 * cnt)
result[height][1] += ((num - height) * cnt)
if num < height:
result[height][0] += ((height - num) * cnt)
result[height][1] -= ((height - num) * cnt)
result = sorted(result, key = lambda x : [x[0], -x[2]])
# 블록 수 체크
for ans in result:
if ans[1] >= 0:
print(ans[0], ans[2])
break
포기 하지 않는 자는 아름답다! 와 내가 거의 제일 빨라!ㅎㅎ 사람들 풀이가 진짜 다양하네~
5397번 키로거 구현하기
30분 걸렸나? 1406 에디터 문제랑 똑같아서 그 때 배운 스택과 덱으로 해결함.
import sys
from collections import deque
t = int(input())
for _ in range(t):
log = sys.stdin.readline().rstrip()
left = []
right = deque([])
for s in log:
if s == '-':
if left:
left.pop()
elif s == '<':
if left:
right.appendleft(left.pop())
elif s == '>':
if right:
left.append(right.popleft())
else:
left.append(s)
print(''.join(left) + ''.join(right))
3085번 봄보니 사탕 게임
1시간 30분 걸림. 다행히 시간초과는 안났지만 시간도 너무 걸린 것 같고… 코드도 너무 길고 깔끔하게 못 푸나? 다른 사람들도 일단 나보다 빠르긴한데 코드 길이는 비슷하군
import sys
import copy
n = int(input())
board = []
change = []
ans = 0
for _ in range(n):
board.append(list(map(str, sys.stdin.readline().rstrip())))
# (행(0) 또는 열(1))색이 다른 인접한 두 칸 고르기
for i in range(n):
for j in range(n-1):
if board[i][j] != board[i][j+1]:
change.append((0, i, j))
if board[j][i] != board[j+1][i]:
change.append((1, j, i))
# 인접한 두칸 교환 후 가장 긴 같은 사탕 길이 고르기
for check, row, col in change:
plate = copy.deepcopy(board)
if check == 0: #행 인접 교환
plate[row][col], plate[row][col+1] = plate[row][col+1], plate[row][col]
else: #열 인접 교환
plate[row][col], plate[row+1][col] = plate[row+1][col], plate[row][col]
for i in range(n):
rowCandy = 1
colCandy = 1
for j in range(n-1):
if plate[i][j] != plate[i][j+1]:
rowCandy = 1
else:
rowCandy += 1
if ans < rowCandy:
ans = rowCandy
if plate[j][i] != plate[j+1][i]:
colCandy = 1
else:
colCandy += 1
if ans < colCandy:
ans = colCandy
print(ans)
다른 사람들도 거의 비슷하게 풀었군. 그리고 나처럼 deepcopy 안쓰고 swap 한 다음 값 구하고 다시 원복하는 식으로 하셨다.
와 대박이다… 이 코드 대박. 시간이 진짜 짧게 드네. 이 코드 뭔가 비효율적일 것 같은데 그러지가 않잖아? 인접한 사탕이 같은지 다른지 상관없이 일단 swap해버리네. **아!!! 대박!! 왜 이사람 코드가 효율적인지 알겠다. 나 포함 다른 사람들은 스왑 한 다음 전체를 탐색함. 사실 스왑하고 영향력 있는 부분만 탐색하면 되는데 말이야. 행 두개를 바꿨으면 행 1개와 열 2개 길이만 체크하면 되고, 열 두개를 바꿨으면 열 1개와 행 2개만 검사하면 돼!
bfs처럼 푸심. 모든 (x,y)에서 네 방향으로 스왑하고 각각 마다 이 (x,y) 사탕이랑 같은 길이를 구하게끔 함. 와 대박;;
import sys
input = sys.stdin.readline
N = int(input())
bomboni = [list(input().strip()) for _ in range(N)]
def sol(row, col) :
row_max = 1
for r in range(row+1, N) :
if bomboni[row][col] == bomboni[r][col] :
row_max += 1
else :
break
for r in range(row-1,-1,-1) :
if bomboni[row][col] == bomboni[r][col] :
row_max += 1
else :
break
col_max = 1
for c in range(col+1, N) :
if bomboni[row][col] == bomboni[row][c] :
col_max += 1
else :
break
for c in range(col-1,-1,-1) :
if bomboni[row][col] == bomboni[row][c] :
col_max += 1
else :
break
return max(row_max, col_max)
dr = [0,0,1,-1]
dc = [-1,1,0,0]
ans = 0
for r in range(N) :
for c in range(N) :
for z in range(4) :
nr = r + dr[z]
nc = c + dc[z]
if 0 <= nr <N and 0 <= nc < N :
bomboni[r][c], bomboni[nr][nc] = bomboni[nr][nc], bomboni[r][c]
ans = max(ans, sol(r, c), sol(nr, nc))
bomboni[r][c], bomboni[nr][nc] = bomboni[nr][nc], bomboni[r][c]
print(ans)
하 그래도 실버2도 벗어났당~
2178번 미로 탐색
25분 걸림. bfs(넓이우선탐색, 인접한 것 먼저 탐색 )의 진짜 전형적인 문제여서 좋은 문제였다! cnt 를 어디에 넣어야하는지 고민 좀 했다!
import sys
from collections import deque
n, m = map(int, input().split())
maze = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(n)]
def bfs():
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False for _ in range(m)] for _ in range(n)]
q = deque([(0,0,0)])
visited[0][0] = True
while q:
x, y, cnt = q.popleft()
cnt += 1
if (x, y) == (n-1, m-1):
print(cnt)
break
for i, j in d:
if 0 <= x + i < n and 0 <= y + j < m:
if visited[x+i][y+j] == False and maze[x+i][y+j] == '1':
q.append((x+i, y+j, cnt))
visited[x+i][y+j] = True
bfs()
와 이것도 좋은데 아예 미로 자체에 몇번째 스텝인지 적어놓는 방법도 좋네. 오히려 이게 더 확장성 있을 수도?
def next(x, y):
Q.append((x,y))
while Q:
# print(Q)
x,y =Q.popleft()
for i in range(4): #상하좌우 확인
new_x=x+dx[i]
new_y=y+dy[i]
if 0<=new_x<n and 0<=new_y<m:
if matrix[new_x][new_y]==1 :
Q.append((new_x,new_y))
matrix[new_x][new_y]=matrix[x][y]+1
return matrix[n-1][m-1]
print(next(0,0))
2667 지도 내 단지 개수와 단지 내 집 개수 세기
30분 걸림. 이것도 전형적인 문제. 많이 풀었던 섬 찾기 문제… 좀 달랐던 건 단지 내에 집이 몇개 있는지 추가로 구해야했음. 그리고 한번 틀렸는데 sort() 해야하는데 sort 해서 정렬이 안됐어 힝
import sys
from collections import deque
n = int(input())
map = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
visited = [[False for _ in range(n)] for _ in range(n)]
block = []
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs(i, j, cnt):
house = 1
q = deque([(i, j)])
while q:
x, y = q.popleft()
for dx, dy in d:
if 0 <= x+dx < n and 0 <= y+dy < n:
if visited[x+dx][y+dy] == False and map[x+dx][y+dy] == 1:
visited[x+dx][y+dy] = True
house += 1
map[x+dx][y+dy] = cnt
q.append((x+dx, y+dy))
return house
cnt = 0
for i in range(n):
for j in range(n):
if visited[i][j] == False and map[i][j] == 1:
cnt += 1
visited[i][j] = True
map[i][j] = cnt
block.append(bfs(i, j, cnt))
block.sort()
print(cnt)
for num in block:
print(num)
역시 dfs로 푼 사람들이 있군. 근데 신기하게 dfs 인데 재귀 함수로 안 쓰고 덱으로 푼 사람이 있네;; 이건 뭐냐 ㅋ bfs 인데 그럼;;