boj 1343 : 폴리오미노

문제 주소: https://www.acmicpc.net/problem/1343

난이도: silver 5

1.문제설명

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

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

• 이때, '.'는 폴리오미노로 덮으면 안 된다.

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

• 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
• 사실 입력에 따른 출력 예시로 보는게 더 편합니다.

XXXXXX -> AAAABB
XX.XX -> BB.BB
XXXX....XXX.....XX -> -1
X -> -1
XX.XXXXXXXXXX..XXXXXXXX...XXXXXX -> BB.AAAAAAAABB..AAAAAAAA...AAAABB

2.문제해결 아이디어.

크게 두가지 풀이가 존재하는 것 같습니다.

• 첫번째는 내장함수 replace를 사용하여 greedy하게 푸는 방법
• 두번째는 replace를 사용하지않고 구현 + greedy한 느낌으로 푸는 방법

3.문제접근법

1. replace 내장함수 사용하는 경우
   replace 내장함수는 문자열의 좌측부터 특정 문자열을 원하는 문자열로 교체해줍니다.
   욕심을 내어 XXXX를 먼저 AAAA로 바꾸고 나머지 XX를 BB로 바꾸면됩니다.
   그다음 X가 한개 이상 문자열에 포함되었다면 -1을 출력하면 됩니다.

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

2. 구현 + greedy
   논리의 전개는 대략적으로 아래와 같습니다. 디테일한 부분은 코드를 보면 이해가 가능합니다.
   1. 문자열을 입력받는다.
   2. 문자열이 빌때까지 다음을 반복합니다.
   3. 문자열의 맨 첫 문자를 temp에 저장한다.
   4. temp = . and 반복횟수가 0이면 temp를 return
   5. 아니면 위의 과정을 반복해서 temp에 이어붙히고 .이 나올때까지 반복한다.
   6. 얻어진 piece에 대해서 AAAA, BB로 바꾸는 작업을 진행한다.

4.특별히 참고할 사항

• 내장함수 이해의 중요성
• 첫 느낌은 greedy를 얹은 구현 느낌이였는데
• .을 찍는 부분이 살짝 까다로워서 중간에 코드를 처음부터 새로 짰습니다.
• 처음엔 split을 이용했지만 이렇게하면 .이 연속으로 찍히는 .., ...등의 case를 구현하기 어려웠습니다.

5.코드구현

• replace를 이용한 코드

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

• 구현 + greedy

board = input()
ans = ''
counter = 0
def recur_get_first(x):
    global counter
    temp = x[0]
    if x[0] == '.' and counter == 0:
        return temp
    if x[0] == '.' and counter != 0:
        return ''
    if len(x) == 1:
        return temp
    else:
        counter += 1
        return temp + recur_get_first(x[1:])

while board:
    piece = ''
    counter = 0
    piece = recur_get_first(board)
    board = board[len(piece):]
    if piece == '.':
        ans += piece
    else:
        if len(piece) % 2 == 1:
            print(-1)
            exit(0)
        else:
            _rest = len(piece) % 4
            _quotient = _rest // 2
            ans += ('AAAA' * (len(piece) // 4) + 'BB' * _quotient)

print(ans)