폴리오미노

1343번: 폴리오미노

 

나의 풀이

import sys

def _ch_pr(now_pr):
    if ((now_pr % 2) != 0):
        return False
    return ('AAAA'*(now_pr // 4) + 'BB'*((now_pr % 4) // 2))
    
def _pr(n):
    for i in range(len(n)):
        if (n[i] == ''):
            continue
        if _ch_pr(len(n[i])): # 덮을 수 있으면
            n[i] = _ch_pr(len(n[i]))
        else: # 없으면
            return -1
    return '.'.join(n)

n = sys.stdin.readline().rstrip().split('.')
print(_pr(n))

 

시간 복잡도

_pr 함수 : 입력 배열을 순회하며 폴리오미노 체크 및 변환 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )