[Baekjoon] 1343번 폴리오미노

문제

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

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

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

입력

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

출력

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

예제

Example 1:

Input: 
XXXXXX
Output: 
AAAABB

Example 2:

Input:
XX.XX
Output:
BB.BB

Example 3:

Input:
XXXX....XXX.....XX
Output:
-1

Example 4:

Input:
X
Output:
-1

Example 5:

Input:
XX.XXXXXXXXXX..XXXXXXXX...XXXXXX
Output:
BB.AAAAAAAABB..AAAAAAAA...AAAABB

조건

시간 제한 : 2초

메모리 제한 : 128 MB

풀이과정

풀이

s = str(input().rstrip())
ans = ""
# -1나올 경우
fine = 0
count = 0
for i in s:
  if i == ".":
    if count%2 == 1:
      fine = 1
      break
    else:
      while(count >= 4):
        ans += "AAAA"
        count -= 4
      if count == 2:
        count -= 2
        ans += "BB"
    count = 0
    ans += "."
  else:
    count+=1

#마지막
if count %2 == 1:
  fine = 1
else: 
  while(count >= 4):
    ans += "AAAA"
    count -= 4
  if count == 2:
    count -= 2
    ans += "BB"

if fine == 0:
  print(ans)
elif fine == 1:
  print("-1")

스트링에서 .이 아닌 경우면 X의 수를 count한다. .이라면 count한 수가 홀수면 fine을 1로 주어서 -1이 프린트되도록 하고 짝수라면 AAAA가 가능하면 먼저오도록(사전순) 조건에 맞게 ans에 추가해준다. 그리고 마지막으로 .을 추가해준다.

한편 .일때만 count한것을 반영하기 때문에 마지막 부분이 반영되지 않으므로 마지막부분을 추가해준다.