[백준 1343번] 폴리오미노 (python)

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

 

기록

(greedy 1일차) 처음 풀면서는 직접 구현했다가 나중에 다른 코드들 보니까 replace 사용해서 푸는 방법도 있길래 시간 비교해보려고 각각 구현했다! 그래서 위의 제출은 replace로 구현한 코드, 아래 제출한 코드는 반복문 돌면서 문자 바꾸는 과정을 직접 구현한 코드이다. 시간이 생각보다 별로 차이가 안나서 놀랐다.

 

코드

<ver 1>

board = input()

idx = 0
newboard = ''

while idx<len(board):
    if board[idx:idx+4]=='XXXX':
        newboard += 'AAAA'
        idx += 4
    elif board[idx:idx+2]=='XX':
        newboard +='BB'
        idx += 2
    elif board[idx]=='X':
        newboard = -1
        break
    else :
        newboard += board[idx]
        idx += 1

print(newboard)

먼저 내가 구현한 코드인데 배열 한 번 돌면서 우선순위를 'AAAA' 바꾸기 -> 'BB'로 바꾸기로 두어 실행하고, 두 가지 조건 만족하지 않고 해당 요소가 'X'라면 바로 중지하도록 했다. 

 

<ver2>

board = input()

board = board.replace('XXXX', 'AAAA')
board = board.replace('XX', 'BB')

if 'X' in board: print(-1)
else: print(board)

이 코드 역시 우선순위를 'AAAA'로 치환, 'BB'로 치환으로 두고 바뀌지 않은 'X' 문자가 있는지 확인한다.

 

ver1은 반복문 한번 돌고 심지어 멈춤조건도 있어서 중간에 멈추기도 한다. 스트링 += 스트링에서 시간이 소요되는 건가 싶다.

ver2는 replace함수로 배열 두 번 돌고, 마지막 X 가 있는지 확인할 때 배열 한 번 더 돌면 시간이 꽤 소요될 것 같은데 생각보다 시간이 차이가 안난다. 왜지??

 

<ver3>

board = input()

idx = 0
newboard = []
while idx<len(board):
    if board[idx:idx+4]=='XXXX':
        newboard.append('AAAA')
        idx += 4
    elif board[idx:idx+2]=='XX':
        newboard.append('BB')
        idx += 2
    elif board[idx]=='X':
        newboard = ['-1']
        break
    else :
        newboard.append(board[idx])
        idx += 1

print(''.join(newboard))

스트링 합치기할때마다 새로 만들어진 객체가 GC의 대상이 되기 때문에 성능이 안 좋다고 알게 되서, newboard를 리스트로 형태로 하고 join으로 출력하도록 바꿔봤는데 기존 시간과 똑같았다.. 흠.....