[코테] 백준 그리디 1343번 문제

1343번 : 폴리오미노

문제 링크

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

문제 설명

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

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

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

입력

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

출력

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

문제 풀이

# 보드판 입력 받기
plate = input()

# 'X'를 fint해서 index가 -1이 아닐때까지 반복
while 'X' in plate :
    
    # 'X', '.' find한 index 저장
    x_idx = plate.find('X')
    coma_idx = plate.find('.', x_idx)
    
    # 남은 '.'가 없으면 배열의 길이를 coma_idx에 저장 (배열끝까지 조회하기 위해)
    if coma_idx == -1 : 
        coma_idx = len(plate)
   
    # 변환해야 되는 X이 개수를 확인해서 홀수면 변환못하므로 반복문 나가기
    pol_cnt = coma_idx - x_idx 
    if pol_cnt % 2 != 0 :
        break
    
    # plate에 변환해야하는 'X'부분을 'AAAA'와 'BB'로 변환
    plate = plate[:x_idx] + (pol_cnt // 4) * 'AAAA' + (pol_cnt % 4) * 'B'  + plate[coma_idx:]

# plate에 'X'가 남아있으면 -1 출력, 아니면 plate 출력
if 'X' in plate : 
    print(-1)
else : 
    print(plate)