백준 1343: 폴리오미노

[Silver V] 폴리오미노 - 1343

문제 링크

성능 요약

메모리: 31256 KB, 시간: 40 ms

분류

구현, 그리디 알고리즘

문제 설명

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

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

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

입력

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

출력

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

---

문제 풀이

아이디어

BB를 먼저 다 찾아놓고, 다 돌면서 AAAA를 새로 넣자 -> 근데 비효율

'X'를 만나면 count를 증가시키고, count가 2가 되면 result 리스트에 'BB'를 넣는다. 그리고 '.'을 만났을 때 만약 count가 홀수면 'XXX.'이면 생성 불가능이므로 result에 -1을 선언하고 루프를 빠져나온다. count가 홀수가 아니면 '.'을 추가.

루프를 다 돌고 result가 -1이거나 result 배열 길이가 원래 data 길이와 다르면 답으로 -1을 출력한다.

아닌 경우에는 'BBBB'인 경우만 'AAAA'로 교체해준다.

너무 복잡해서 다른 풀이를 찾아보니까 그냥 replace로 간단하게 풀더라.. 왜 실버 5인지 알았다..

코드

import sys

data = list(sys.stdin.readline().rstrip())

count = 0
result = []
for i in data:
  if i == 'X':
    count += 1
    if count == 2:
      result.append('BB')
      count = 0
      continue
  if i == '.':
    if count % 2 == 1:
      result = -1
      break
    else:
      result.append('.')

if result == -1 or len(''.join(result)) != len(data):
  print(-1)
else:
  count = 0
  answer = []
  for i in range(len(result)):
    if result[i] == '.':
      count = 0
      answer.append('.')
    else:
      count += 1
      if count == 2:
        answer.append('AAAA')
        count = 0
      if (count == 1 and i == len(result) - 1) or (count == 1
                                                   and result[i + 1] == '.'):
        answer.append('BB')
        count = 0
  print(''.join(answer))