[BOJ] 폴리오미노 - Python

문제

---

1343번: 폴리오미노

 

 

풀이

---

본 문제는 그리디를 사용해서 풀이했습니다.

폴리오미노 'AAAA'의 문자 개수가 폴리오미노 'BB'의 문자 개수의 배수이기 때문에

'AAAA' 선택 후 'BB' 선택이라는 현재 시점에서의 최선의 선택지가 있기 때문입니다.  

 

연속된 'X' 와 '.' 에 대해 다른 태도를 취해야하므로 ('X' 는 교체, '.' 는 통과) 'X' 와 '.' 을 나눠서 새로운 배열에 저장해 주었는데,

문자열을 나눠서 새로운 배열 answer_lst 에 넣어주는 과정은 divide_board 함수를 이용했습니다. 

 

divide_board 함수 내용은 다음과 같습니다.

---

1. 인덱스 슬라이싱을 위한 시작 포인트를 지정하기 위한 point 변수
2. 한 문자로만 이루어진 문자열을 저장하기 위한 answer_lst
3. 입력받은 board 문자열을 0 번째 인덱스부터 (len(board) - 2) 번째 인덱스까지 살펴봅니다.
4. 현재 보고 있는 문자와 다음 문자를 비교해서 다르면, 시작 point 부터 현재 인덱스 i 까지 슬라이싱해 배열에 추가합니다.
5. 시작 point 는 현재 인덱스의 다음 인덱스로 초기화 해줍니다.
6. (len(board) - 2) 번째 인덱스 (현재 i == len(board) - 2) 까지 살펴봤으면 현재 시작 point 부터 문자열 끝까지 (i + 1번째) 슬라이싱해 배열에 추가해줍니다.

---

'X' 로 이루어진 문자열의 경우는 'X' 의 개수가 홀수일 때만 덮을 수 없으므로 이에 대한 분기처리를 해주었습니다.

---

💡 풀이 코드는 아래와 같습니다. 

input_board = input()

# 입력 -> 'XX.XX'
# 출력 -> ['XX', '.', 'XX'] 
def divide_board(board):
    point = 0
    answer_lst = []
    
    # 다음 인덱스가 없을 경우(문자열 board 길이가 1)의 예외처리
    if len(board) == 1:
        return [board]

    for i in range(len(board) - 1):
        if board[i] == board[i + 1]:
            continue
        elif board[i] != board[i + 1]:
            answer_lst.append(board[point:i + 1])
            point = i + 1

    answer_lst.append(board[point:i + 2])
    return answer_lst


def solution(board):
    result_lst = []

    for target in divide_board(board):
        # 문자 '.'일 경우 그대로 추가
        if target[0] == '.':
            result_lst.append(target)
        # 문자 'X'일 경우 치환해서 추가
        else:
            num = len(target)
            # 치환 불가일 경우
            if num % 2 == 1:
                return -1
            else:
                result_lst.append('A' * (num // 4) * 4 + 'B' * (num % 4))

    return ''.join(result_lst)

print(solution(input_board))

---

... 리팩토링 과정에서 replace 함수를 이용해 더 간편하게 풀 수 있다는 것을 깨달았습니다.

board = input()

# 'AAAA'로 먼저 치환
board = board.replace('XXXX', 'AAAA')
board = board.replace('XX', 'BB')

print(-1) if 'X' in board else print(board)