생명과학부 랩 인턴
simulation
평균 : 180'
sol : 217' 07''
- 수행 시간 : 791ms
- 메모리 : 26MB
New skills
- Queue에 대해 더 공부해야 한다.
Simulation에 있어서 데이터의 삭제가 들어가는 순간 list 활용은 시간 초과의 주범이 되므로, Queue를 활용하는 방법을 더 공부해야 한다.- 이번 문제에서 2차원 큐를 써서 겹치는 곰팡이들에 대해 간단히 삭제하는 과정을 고려해봤지만, 기본기 부족인지 아니면 없는 기능인지 모를 원인으로 접목은 실패. 리스트로 해결했다.
- 시뮬레이션 문제에서 데이터 구조의 삽입, 삭제는 수행 시간에 매우 치명적인 영향을 주는 편인데, 그동안은 삭제를 해도 그냥 가져가는 경우가 많았다.
하지만 이번에 새로 시도해본 배열 truncate 기술을 쓰니까 시간이 매우 효과적으로 줄었다!!!
molds.sort(key=lambda x: [x[0], x[1]]) return molds[l:]여기서 보면 죽은 곰팡이들에 대해 좌표를 (-1, -1)로 적고, 이를 정렬하여 앞에서부터 죽은 곰팡이 갯수만큼 삭제하여 리턴해주는 코드이다.
이렇게 하니까 시간복잡도가 약 20% 줄어들었다!
# k : # of mold
n, m, k = map(int, input().split())
# x, y : mold pos / s : dis per sec of mold / d : dir / b : size of mold
molds = []
answer = 0
for _ in range(k):
# molds[i][0] : i'th mold's i pos / ...
molds.append(list(map(int, input().split())))
# collect nearest mold in col
def collect():
global answer, molds
molds.sort(key=lambda x: [x[1], x[0]])
# index starts from 1!
for col in range(1, m + 1):
for mold in molds:
# if there's mold in search area(col)
if mold[1] == col:
# print('collected ', mold)
answer += mold[4]
molds.remove(mold)
break
# if no mold, pass
else:
continue
move()
molds = collision_check()
# molds move
def move():
for mold in molds:
if mold[4] == 0:
continue
d = 0
while d != mold[2]:
# Up
if mold[3] == 1:
if mold[0] > 1:
mold[0] -= 1
else:
mold[3] = 2
mold[0] += 1
d += 1
continue
# Down
if mold[3] == 2:
if mold[0] < n:
mold[0] += 1
else:
mold[3] = 1
mold[0] -= 1
d += 1
continue
# Right
if mold[3] == 3:
if mold[1] < m:
mold[1] += 1
else:
mold[3] = 4
mold[1] -= 1
d += 1
continue
# Left
if mold[3] == 4:
if mold[1] > 1:
mold[1] -= 1
else:
mold[3] = 3
mold[1] += 1
d += 1
continue
def collision_check():
molds.sort(key=lambda x: [x[0], x[1], -x[4]])
l = 0
for i in range(len(molds) - 1):
cur_i, cur_j, cur_s = molds[i][0], molds[i][1], molds[i][4]
for j in range(i + 1, len(molds)):
if molds[j][4] != 0 and cur_i == molds[j][0] and cur_j == molds[j][1]:
# print('killed mold is ', molds[j])
molds[j][0], molds[j][1], molds[j][4] = -1, -1, 0
l += 1
else:
break
molds.sort(key=lambda x: [x[0], x[1]])
return molds[l:]
collect()
print(answer)