[Python] 백준 1343번 - 폴리오미노

https://www.acmicpc.net/problem/1343

1343번: 폴리오미노

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 구현
 - 그리디 알고리즘

문제

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

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

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

입력

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

출력

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

 

---

 

이 문제를 다풀고나서 나는 멍청하다는 걸 알았다.

 

우선 내가 멍청하게 푼 방법을 보자.

 

import sys
input = sys.stdin.readline

s = input().rstrip()

result = ""
dot = ""
cnt = 0
for i in range(len(s)):
    if s[i] == ".":
        a = cnt // 4
        b = cnt % 4
        if cnt % 2 != 0:
            result = "-1"
            cnt = 0
            break
        if a != 0:
            result += "AAAA" * a
        if b != 0:
            result += "BB"
        result += "."
        cnt = 0
    else:
        dot = ""
        cnt += 1

if cnt % 2 != 0:
    result = "-1"
else:
    a = cnt // 4
    b = cnt % 4
    if a != 0:
        result += "AAAA" * a
    if b != 0:
        result += "BB"
print(result)

난 문제를 보자마자

 

문자열의 길이가 최대 50밖에 안된다는 사실에 아 그냥 하나하나 확인하면 되겠구나...

 

라는 생각을 했다.

 

그 덕분에 만들어진 코드이다. 굉장히 비효율적이다.

---

문제를 다 풀고나서 생각난 코드이다.

 

import sys
input = sys.stdin.readline

s = input().rstrip()

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

if 'X' in s:
    print(-1)
else:
    print(s)

우리에겐 replace라는 아주 좋은 기능이 있었다...

 

맨날 일하면서도 쓰는건데 왜 오늘따라 생각이 안 난 건지 잘 모르겠다.

 

머리가 살짝 아파서그런가 컨디션이 별로라서 그런가.