[백준] falling apples - 13732번

 

문제

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

13732번: Falling Apples

 

입출력

 

 

풀이 방법

문제가 영어로 만들어져 있어 당황스러울 수 있지만, 요구하는 바가 간단하다.

'a' 가 apple, '#'이 벽으로 중력에 의해 사과들이 아래로 떨어진 후의 모습을 구현하면 되는 것이다.

 

이런 시뮬레이션 유형의 문제에 요즘 재미를 붙여 여러개 풀고 있는 중이다ㅎ

 

각설하고, 처음 생각한 방법으로는 

1. 아래의 row 부터 사과를 체크하며 직접 하나씩 내린다.

 무조건 답이 나오는 방법이겠지만, 여기서의 row가 50,000개가 max여서 각각의 사과를 다 step별로 내려주기엔 시간이 오래걸릴 수 있다.

 

때문에,

 

2. col들을 기준으로 아래에서 내려가면서 'a' 와 '#' 만 stack에 쌓듯이 쌓아간다.

 이때, a는 식별할 수 있는 값으로 (나는 '-1'로했다) #는 현재 #의 row index 값으로 쌓았다. 이유는 벽이 있으면 그 위로의 사과들은 벽위로 쌓여야 하기 때문이다.

 

예제 1번의 예시로 보면 

1번 col 스택: [1, -1]

2번 col 스택: [-1]

3번 col 스택: [2, -1]

 

각 col의 생성이 끝나면, 각 col의 스택의 처음부터 scan하며 -1이라면 아래에서부터 쌓아주고 -1이 아닌 값을 마주했다면 그 값 이후의 값부터는 -1이 아닌 값 즉 '해당 인덱스 -1' 한 row에 사과를 쌓아주면 되는 것이다.

 

즉 위의 col 스택을 바꿔보면

1번 col 스택: [1, 0]

2번 col 스택: [2]

3번 col 스택: [2, 1]

 

이 결과가 되는 것이고 이 row와 col 값에 맞추어 새로운 answer 배열에 넣어주면 된다!

 

r, c = map(int, input().split())
world = []

for i in range(r):
    world.append(list(input()))

answerWorld = [['.' for _ in range(c)] for _ in range(r)]

for i in range(c):
    stack = [] # 그냥 사과: -1, idx: 벽
    for j in range(r):
        if world[r-j-1][i] == 'a':
            stack.append(-1)
        elif world[r-j-1][i] == '#':
            stack.append(r-j-1)
    newIdx = r-1
    for value in stack:
        if value != -1:
            answerWorld[value][i] = '#'
            newIdx = value

        else:
            answerWorld[newIdx][i] = 'a'

        newIdx -= 1



for i in range(r):
    for j in range(c):
        print(answerWorld[i][j], end='')
    print()

 

 

 

끘~~