BOJ 1343번 폴리오미노 python 풀이

🔷 🟩 1. 문제 설명

민식이는 아래와 같은 폴리오미노 조각을 가지고 있습니다:

• AAAA: 4개의 칸을 덮는 폴리오미노
• BB: 2개의 칸을 덮는 폴리오미노

보드판에는 'X'와 '.'로 이루어진 문자열이 주어지고, 민식이는 모든 'X'를 이 폴리오미노 조각으로 빈틈 없이 덮고자 합니다. 단, '.'는 절대로 덮으면 안 됩니다.

민식이의 목표는:

• 주어진 보드판에서 모든 'X'를 겹침 없이, 오직 AAAA, BB 폴리오미노로만 덮는 것
• 덮는 것이 불가능하면 -1을 출력
• 가능한 경우에는 사전순으로 가장 앞서는 결과를 출력

---

🔷 🟩 2. 문제 출처 및 링크

BOJ 1343번 - 폴리오미노

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

---

🔷 🟩 3. 나의 풀이 아이디어 및 접근 전략

🟨 핵심 아이디어 요약

• 'X'가 연속으로 등장하는 덩어리 단위로 문제를 쪼갭니다.
• 하나의 덩어리 안에서 'X'의 개수(cnt)를 세고, 그 개수를 바탕으로 "AAAA"와 "BB"로 나눠서 덮습니다.
• 이때 반드시 'X'의 개수는 짝수여야만 덮을 수 있습니다.
• 이유: AAAA는 4개, BB는 2개를 덮기 때문에 홀수는 덮을 수 없습니다.

🟨 구체적 처리 방식

1. 입력 문자열을 list로 받아 문자 하나하나 수정 가능하게 합니다.
2. 반복문을 돌며 'X'가 나올 때마다 개수를 누적합니다.
3. 'X'가 끝나고 '.'가 나오거나 문자열이 끝나면, 지금까지 누적한 'X'의 개수를 바탕으로 "AAAA"와 "BB"로 교체합니다.
4. 이때:
   • 홀수 개면 → 바로 -1 출력
   • 4개 이상이면 "AAAA"부터 최대한 채움
   • 남는 2개는 "BB"로 채움
5. 실제로 리스트 내부 값을 바꾸기 위해 ptr(포인터)을 이용하여 현재 교체 위치 추적

🟨 주요 변수 역할

변수명	설명
st	입력된 문자열을 리스트로 바꾼 것
cnt	연속된 'X'의 개수를 누적하는 변수
ptr	교체해야 할 위치를 추적하는 포인터
i	반복문 인덱스 (현재 탐색 중인 위치)

---

🔷 🟩 4. 전체 코드 구현

st = list(input())
cnt = 0
ptr = 0

for i in range(len(st) + 1):
    if i < len(st) and st[i] == 'X':
        cnt += 1
    else:
        if cnt % 2 == 1:
            print(-1)
            exit()
        elif cnt > 0:
            while cnt >= 4:
                for j in range(ptr, ptr + 4):
                    st[j] = 'A'
                ptr += 4
                cnt -= 4
            while cnt >= 2:
                for j in range(ptr, ptr + 2):
                    st[j] = 'B'
                ptr += 2
                cnt -= 2
        ptr = i + 1
        cnt = 0

for i in st:
    print(i, end='')

---

🔷 🟩 5. 코드 라인별 세부 해설

🟨 입력 문자열을 리스트로 변환

st = list(input())

문자열을 리스트로 변환 → 이후에 직접 문자를 수정해야 하기 때문입니다.

🟨 초기 변수 선언

cnt = 0
ptr = 0

• cnt: 연속된 'X'의 개수를 저장
• ptr: 교체할 시작 위치. 실제로 "AAAA" 또는 "BB"를 어디에 넣을지 결정

🟨 전체 문자열 순회

for i in range(len(st) + 1):

+1을 해주는 이유는 문자열 마지막에 'X'가 있을 경우도 처리해야 하기 때문입니다.

🟨 'X'가 연속되는 구간 처리

if i < len(st) and st[i] == 'X':
    cnt += 1

현재 문자가 'X'일 경우 cnt를 1 증가시켜 연속된 'X' 개수를 세기 위함입니다.

🟨 'X' 덩어리 끝 처리: 홀수 불가 조건

else:
    if cnt % 2 == 1:
        print(-1)
        exit()

지금까지 센 'X' 개수가 홀수면 덮을 수 없으므로 바로 종료합니다.

🟨 AAAA로 덮기

while cnt >= 4:
    for j in range(ptr, ptr + 4):
        st[j] = 'A'
    ptr += 4
    cnt -= 4

사전순을 만족하기 위해 "AAAA"부터 최대한 채웁니다.

🟨 BB로 나머지 덮기

while cnt >= 2:
    for j in range(ptr, ptr + 2):
        st[j] = 'B'
    ptr += 2
    cnt -= 2

"AAAA"로 못 채운 2개는 "BB"로 채웁니다.

🟨 포인터, 카운터 초기화

ptr = i + 1
cnt = 0

다음 'X' 덩어리를 처리하기 위한 초기화입니다.

🟨 결과 출력

for i in st:
    print(i, end='')

최종 결과 리스트를 다시 문자열처럼 출력합니다.

---

🔷 🟩 6. 개선된 코드 (시간/공간 복잡도 최적화 방향)

🟨 개선 이유

• 리스트 내부를 직접 수정함 → ptr, for j 반복문으로 복잡함
• 불필요한 변수와 반복문 중첩
• 가독성이 떨어짐

🟨 개선 코드 전체

board = input()
result = ''
i = 0

while i < len(board):
    if board[i] == 'X':
        count = 0
        while i < len(board) and board[i] == 'X':
            count += 1
            i += 1
        if count % 2 == 1:
            print(-1)
            exit()
        result += 'AAAA' * (count // 4)
        result += 'BB' * ((count % 4) // 2)
    else:
        result += '.'
        i += 1

print(result)

---

🔷 🟩 7. 개선 코드 라인별 상세 해설

🟨 입력 처리 및 결과 저장 초기화

board = input()
result = ''
i = 0

문자열을 그대로 받고, 결과는 result라는 문자열에 누적합니다.

🟨 문자열 전체 순회

while i < len(board):

인덱스를 직접 제어하며 전체 문자열을 순회합니다.

🟨 'X' 덩어리 개수 세기

if board[i] == 'X':
    count = 0
    while i < len(board) and board[i] == 'X':
        count += 1
        i += 1

연속된 'X'가 몇 개인지 카운트하며 i도 동시에 증가시켜 다음 위치로 이동합니다.

🟨 홀수 불가능 조건

if count % 2 == 1:
    print(-1)
    exit()

'X' 개수가 홀수라면 덮을 수 없기 때문에 종료합니다.

🟨 AAAA, BB 덮기 처리

result += 'AAAA' * (count // 4)
result += 'BB' * ((count % 4) // 2)

4개씩 AAAA로 최대한 덮고, 남는 2개는 BB로 덮습니다.

🟨 '.' 처리

else:
    result += '.'
    i += 1

'.'은 그대로 유지해야 하므로 결과에 그대로 추가합니다.

🟨 최종 출력

print(result)

덮은 결과 전체를 출력합니다.