Baekjoon 1343 | 폴리오미노 (Python)

📌문제

SILVER5 / 구현 / 그리디 알고리즘

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

📌문제 분석 및 설계

문제를 봤을 때,

X뭉터기랑 .뭉터기를 분리하는게 이 핵심이라고 생각했다.

 

따라서 아래와 같은 요소들로 설계를 했다.

1. split를 통해서 분리

2. 나누기로 A,B삽입

3. 반례로 .만 있을때 케이스 분리(자꾸 틀려서 그제야 반례찾으면서 알게 됨)

 

하지만... replace를 쓴다면 굉장히 간단하게 끝난다..하핳

📌알게된 팁

문자열에 +연산을 계속하면, 문자열은 불변(immutable) 이라서 O(N^2) 성능이 될 수 있다 

👉 리스트에 append() 해서 나중에 "".join()으로 합치는 게 더 효율적!!

📌소스 코드

처음코드는 아래와 같고 

original=input()
polyomino=original.split('.')
A='AAAA'
B='BB'
def replace_polyomino():
    result=[]
    for i,p in enumerate(polyomino):
        if 'X' in p:
            length=len(p)
            if length%2==1:
                return -1
            else:
                a,b=divmod(length,4)
                b=b//2
                result.append(A * a + B * b)
                if i!=len(polyomino)-1:
                    result+='.'
        else:
            if i!=len(polyomino)-1:
                result+='.'
    return result

if 'X' not in original:
    print(original)
else:
    result=replace_polyomino()
    print(''.join(result) if result != -1 else -1)

 

맞춘후 더 나은 코드를 알고자 GPT에게 물어봤더니 아래와 같이 수정해줬다. 훨 간단한 코드다..

original = input()
polyomino = original.split('.')
A = 'AAAA'
B = 'BB'

def replace_polyomino():
    result = []
    
    for i, p in enumerate(polyomino):
        if p:  # 빈 문자열이 아니면 (즉, 'X' 포함)
            length = len(p)
            if length % 2 == 1:
                return -1  # 홀수면 불가능
            
            a, b = divmod(length, 4)
            b //= 2
            result.append(A * a + B * b)
        result.append('.')  # 각 구간 사이에 '.' 추가

    return "".join(result[:-1])  # 마지막 '.' 제거 후 문자열 변환

# 전부 '.'이면 그대로 출력
if 'X' not in original:
    print(original)
else:
    result = replace_polyomino()
    print(''.join(result) if result != -1 else -1)

 

그리고 replace를 쓰면 아래와 같이 너무너무너무너무 간단해진다....

S = input()
S = S.replace("XXXX", "AAAA")
S = S.replace("XX", "BB")

print(S if "X" in S else -1)