백준 1343[폴리오미노]

1. 문제설명

문제 URL : https://www.acmicpc.net/problem/1343

 

이 문제는 주어진 문자열에서 ‘X’로 이루어진 모든 부분을 ‘AAAA’ 또는 ‘BB’로 대체하는 문제입니다. ‘X’를 덮을 수 있는 방법은 두 가지뿐이며, 4개의 연속된 ‘X’는 ‘AAAA’로, 2개의 연속된 ‘X’는 ‘BB’로 변환할 수 있습니다. 그 외의 경우에는 덮을 수 없기 때문에 불가능한 경우를 처리해야 합니다. 예를 들어, 입력이 “XX….XXXX”일 경우, 가능한 변환은 “BB….AAAA”입니다. 만약 덮을 수 없는 패턴이 존재할 경우, -1을 출력합니다.

2. 정답코드

import sys
input = sys.stdin.readline

# 보드를 입력받아 리스트로 변환
board = list(input().rstrip())

def sol():
    cnt = 0     # 'X'의 개수를 세는 카운터
    ans = ''    # 결과를 저장할 문자열

    for i in range(len(board)):
        if board[i] == 'X':     # 현재 문자가 'X'인 경우
            cnt += 1            # 'X'의 개수를 증가시킴
            if cnt == 4:        # 'X'가 4개가 되면
                ans += 'AAAA'   # 'AAAA'로 변환하여 추가
                cnt = 0         # 카운터를 초기화
        else:                   # 현재 문자가 '.'인 경우
            if cnt == 0:        # 'X'가 없는 경우 (이전 문자가 '.')
                ans += '.'      # 그대로 '.'을 추가
            elif cnt == 1:      # 'X'가 1개일 때는 덮을 수 없으므로 -1 반환
                return -1
            elif cnt == 2:      # 'X'가 2개일 때는 'BB'로 덮을 수 있음
                ans += 'BB.'    # 'BB'를 추가하고 '.'도 추가
                cnt = 0         # 카운터를 초기화
            else:               # 'X'가 3개일 경우 덮을 수 없으므로 -1 반환
                return -1
    
    # 반복문이 끝난 후 남아있는 'X'의 개수를 확인
    if cnt == 0:  # 남은 'X'가 없는 경우
        return ans  # 결과 반환
    elif cnt == 1:  # 'X'가 1개일 때는 덮을 수 없으므로 -1 반환
        return -1
    elif cnt == 2:  # 'X'가 2개일 때는 'BB'로 덮을 수 있음
        ans += 'BB'
        return ans  # 결과 반환
    else:  # 'X'가 3개일 경우 덮을 수 없으므로 -1 반환
        return -1

# 결과 출력
print(sol())

 

3. 코드설명

1) 변수 초기화

• board는 입력받은 문자열을 리스트로 변환하여 저장합니다.
• cnt는 ‘X’의 개수를 세기 위한 변수로, 초기값은 0입니다.
• ans는 최종 변환 결과를 저장할 문자열입니다.

2) 보드 탐색 및 변환 수행

• 보드를 순차적으로 탐색하며, ‘X’의 연속된 개수를 세어 그에 맞는 패턴(‘AAAA’ 또는 ‘BB’)으로 변환합니다.
• 만약 4개의 ‘X’가 연속으로 나오면 ‘AAAA’로 변환하여 ans에 추가하고, cnt를 초기화합니다.
• ’.’이 나오면, 지금까지의 ‘X’ 개수를 확인하여 적절한 패턴을 ans에 추가합니다. 만약 ‘X’의 개수가 덮을 수 없는 1개나 3개라면 함수는 -1을 반환합니다.

3) 남아있는 ‘X’ 처리

• 탐색이 끝난 후에도 ‘X’가 남아있을 수 있습니다. 이 경우 남은 ‘X’의 개수에 따라 ‘BB’로 덮을 수 있는지 확인하고, 덮을 수 없는 경우 -1을 반환합니다.

4) 결과 출력

• 함수 sol()이 반환한 결과를 출력합니다. 만약 -1이 반환되면 덮을 수 없는 상황을 의미합니다.

4. Github으로 확인

coTest/BOJ_EASY/E_BOJ_04_1343.py at main · pcy4196/coTest