[python] 13732 - Falling apples

beans3142 2023. 1. 22. 13:17

https://www.acmicpc.net/problem/13732

13732번: Falling Apples

The input begins with a line containing integers R and C, designating the number of rows and columns of the grid, such that 1 ≤ R ≤ 50 000 and 1 ≤ C ≤ 10. The first line is followed by R additional lines, each designating a row of the grid, from to

www.acmicpc.net

흔히 볼 수 있는 '중력' 문제이다.
그런데 그냥 아무생각없이 O(N^2)과 같은 시간복잡도로 구현하기 쉬운 유형이다.
큐를 이용한다면 한 줄당 O(N)의 시간복잡도로 해결이 가능하다.

from sys import stdin
from collections import deque
input=stdin.readline

n,m=map(int,input().split())
arr=[input().rstrip() for i in range(n)]
line=deque([])
ans=[['' for i in range(m)] for i in range(n)]

for i in range(m):
    for j in range(n):
        if arr[~j][i]=='#':
            ans[~j][i]='#'
            for k in range(len(line)):
                ans[~j+k+1][i]=line[~k]
            line=deque([])
        else:
            if arr[~j][i]=='.':
                line.append('.')
            else:
                line.appendleft('a')
    for k in range(len(line)):
        ans[~j+k][i]=line[~k]
    line=deque([])

for i in ans:
    print(*i,sep='')