Ray`s Tech Lab

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

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

XXXXXX

예제 출력 1 복사

AAAABB

예제 입력 2 복사

XX.XX

예제 출력 2 복사

BB.BB

[내가 한 풀이]

boards = input().split('.')
answer = ''

for board in boards:
    if len(board) % 2 == 1:
        print(-1)
        break
    else:
        if len(board) >= 4:
            answer += 'AAAA' * (len(board) // 4)
        answer += 'BB' * ((len(board) % 4) // 2) + '.'
else:
    print(answer[:-1])

입력으로 받은 전체 보드판(?)을 split()메소드를 활용해 온점(.)을 기준으로 나눠서 리스트로 만든다.

이후 리스트에 대해 순회하는데, 나는 AAAA와 BB라는 폴리오미노만 갖고 있으므로 홀수칸짜리 보드판에 대해서는 폴리오미노를 덮을 수 없다. 이 경우는 2로 나눈 나머지가 1인 경우에 해당하며, 이땐 -1을 출력하고 break.

보드판이 짝수칸이라면 몇 칸인지에 관계없이 폴리오미노로 덮을 수 있는데, 2칸일 경우에만 처음부터 바로 BB를 채우고 2칸이 아니라면 그냥 무지성으로 AAAA만 신나게 깔아주다가 마지막에 2칸만큼 남으면 BB를 덮으면 된다. 어차피 if-else 이하의 코드는 순회한 보드가 짝수칸일테만 실행되므로, 4칸 이상일 때는 보드칸을 4로 나눈 몫만큼 AAAA를 덮어주고, 이후 나머지 칸에 대해 BB를 덮어준다. AAAA를 다 덮고 남은 칸은 len(board) % 4이다. 

마지막엔 출력할 차례. 순회하는 모든 보드판이 죄다 짝수칸이었다면 break문에 의해 비정상적으로 for문이 종료되지 않았으므로 마지막의 for-else문의 print가 실행된다. 이때 answer의 마지막은 온점(.)이므로 슬라이싱하여 그 전까지만 출력하면 정답이다. 

[더 쉬운 풀이]

board = input()
board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")
if 'X' in board:
    board = -1
print(board)

replace메소드를 활용해 처음엔 문자열 내에 등장하는 모든 XXXX를 AAAA로 바꾸고, 이후 다시 문자열 내에 등장하는 모든 XX를 BB로 바꿔주고, 마지막에 X가 남아있다면 -1을 출력하도록 한다.

replace메소드는 replace(old, new, count) 총 3개의 파라미터를 받으며 old는 현재 문자열에서 바꾸고 싶은 놈, new는 새로 바꿀 문자, count는 정수를 받으며 변경할 횟수를 의미한다. count는 optional로 입력하지 않으면 문자열 전체의 old를 new로 바꾼다.