[Greedy/그리디] 백준 1343 폴리오미노 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1343번: 폴리오미노

 

 

 

2. 문제 풀이

 .와 X로 이루어진 문자열이 주어집니다. XXXX는 AAAA로 XX는 BB로 바꾸며, X가 홀수로 남게 되면 -1를 출력합니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 사전순으로 가장 앞서는 답을 출력해야 하므로, X가 4개 이상 연달아 있으면 무조건 AAAA로 먼저 변환해야 합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
board = input().rstrip() + '.'

# 덮어쓰기
new_board = ''
x_cnt = 0
for s in board:
    # X이면 카운트 +1
    if s == 'X':
        x_cnt += 1

    # .이면 정산 후 반영
    else:
        if x_cnt % 2 == 1:
            print(-1)
            break

        new_board += 'AAAA' * (x_cnt//4)
        x_cnt %= 4

        new_board += 'BB' * (x_cnt//2)
        x_cnt = 0
        new_board += '.'

else:
    print(new_board[:-1])

 맨 뒤에 .을 추가해서, 맨 마지막에 남은 X의 개수도 정산합니다. 그리고 맨 마지막 .은 빼고 출력합니다.