[백준] 10703 파이썬 - 유성

문제

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

 

풀이

첫번째 풀이 (틀린 풀이)

공기층을 찾고, 해당 인덱스 위의 유성 층들을 모두 검사했다.

완전탐색으로 풀이해서 시간초과가 났다. 

import sys
import pprint
from copy import deepcopy

input = sys.stdin.readline

r,s = map(int,input().split())
meteor = [list(input().strip()) for _ in range(r)]

# 공기층 index 구하기
air_index = 0
for i in range(len(meteor)):
    if meteor[i] == list('.' for _ in range(s)):
        air_index = i

answer = deepcopy(meteor)

while(True):
    is_collide = False
    for i in range(air_index-1,-1,-1):
        for j in range(len(meteor[i])):
            if meteor[i][j] == 'X' and i+1 < r:
                if meteor[i+1][j] == '.':
                    meteor[i+1][j] = 'X'
                    meteor[i][j] = '.'
                else:                    
                    is_collide = True
                    break     
        if is_collide:
            break   

    if is_collide:
        break
    else:
        answer = deepcopy(meteor)

    air_index += 1


for i in answer:
    print(*i)

 

 

두번째 풀이

생각해보니, 한 열씩 검사하며 유성(X)과 땅(#)의 최소 거리를 구한 후 그 거리만큼 유성들을 내려주면 되는 것이었다.

유성층을 최소거리만큼 아래 열로 내려주면 정답을 구할 수 있다.

 

import sys
import pprint

input = sys.stdin.readline
r,s = map(int,input().split())
meteor = [list(input().strip()) for _ in range(r)]

# 각 열에 대해, 유성과 땅의 최소 거리를 구한다.
dist = int(1e9)
for i in range(s):   
    column = [meteor[j][i] for j in range(r)]
    meteor_idx = 0
    ground_idx = int(1e9)

    # 유성이 존재하는 열만 최소거리 구해야함
    is_exist_meteor = False

    for j in range(len(column)):
        if column[j] == 'X':
            is_exist_meteor = True
            meteor_idx = max(meteor_idx,j)
        if column[j] == '#':
            ground_idx = min(ground_idx,j)

    if is_exist_meteor:
        dist = min(dist,ground_idx-meteor_idx-1)

# 유성들을 모두 dist만큼 아래로 내린다 (아래 행부터 검사한다)
for i in range(r-1,-1,-1):
    for j in range(s):
        if meteor[i][j] == 'X':
            meteor[i+dist][j] = 'X'
            meteor[i][j] = '.'

for i in meteor:
    for j in i:
        sys.stdout.write(j)
    sys.stdout.write('\n')

 

이때 print 를 써서 출력하면 시간초과가 뜬다.

범위가 큰 2차원 문자열 리스트를 출력할 때 print() 대신 sys.stdout.write()를 사용해야 한다.

문자열을 하나하나 출력하는 경우에 print()는 엄청 느릴 수 밖에 없다.

따라서 sys.stdout.write를 사용해주어야 한다.