[백준_1343]폴리오미노_python

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

1343번: 폴리오미노

문제

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

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

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

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

문제 해결

문자열에 대한 이해를 바탕으로 순간에 최선의 선택을 하는 그리디 알고리즘으로 문제를 해결하였다.

X는 'AAAA' 혹은 'BB' 둘 중 하나로만 치환할 수 있고 예제를 보면 4자리의 A가 우선적으로 치환되는 것을 확인할 수 있다.

고로 문제를 그리디적으로 해결한다고 방향을 잡을 수 있다.

첫 번째로 입력받은 문자열을 list배열로 변형한 후 슬라이싱을 통해 수정하는 방법

두 번째로는 '.'를 기준으로 입력을 받고 각 요소의 자릿수가 4의 배수는 'A'로 2자리일 경우에는 'B'로

새로운 배열에 넣는 방식으로 문제를 해결할 수 있다.

 

##1
polio = list(input())#수정.리스트
for i in range(len(polio)):
    if polio[i]=='X':
        if 0<= i  and i+3 < len(polio) and polio[i:i+4]==['X']*4:
            polio[i:i+4] =  ['A']*4
        elif 0<=i and i+1<len(polio) and polio[i:i+2]==['X']*2:
            polio[i:i+2] = ['B']*2
        else:
            print(-1)
            exit(0)
    else:
        continue
print(''.join(polio))
##2
def polio():
    res = []
    s = input().split('.')
    for i in s:
        if len(i) % 2:
            print(-1)
            return
        res.append('AAAA'*(len(i)//4) + 'BB'*((len(i)%4)//2))
    print('.'.join(res))
polio()