[BOJ/Python] 백준 1343번 - 폴리오미노 풀이

📣코딩테스트를 위한 백준 문제 추천 모음

문제

백준 1343번 - 폴리오미노

📁 문제 정의

입력으로 주어진 보드에 .을 제외한 모든 X를 A 또는 B로 바꾸면 되는 문제다. 이때, 연속된 X의 개수가 4개면 AAAA로 2개면 BB로 바꾸면 된다.

접근 방법

이 문제의 보드판의 크기는 최대 50이고 시간제한은 2초이다. 이 문제를 보자마자 그리디 알고리즘이 떠올랐다. 그럼 과연 이 문제를 그리디 알고리즘으로 해결할 경우 최적의 해를 가지게 되는지 검증을 해보자.

이 문제의 경우 XXXX를 AAAA로 XX를 BB로 교체하면 되는데 AAAA는 BB의 배수이기 때문에 항상 최소한의 교체로 최적의 해를 가질 수 있다. 또한 최대 보드 크기가 50인데 시간제한이 2초이므로 그리디 알고리즘으로 풀어도 시간제한이 걸릴 리가 없기 때문에 그리디 알고리즘으로 문제를 해결해 보았다.

💡 문제 해설

총 2가지의 풀이로 문제를 해결하였는데, 두 풀이 모두 board 마지막에 \n가 포함되게 문자열로 입력을 받았다.

첫 번째 풀이는 .또는 \n가 나올 때까지 연속된 X의 개수를 변수 cnt에 저장해주고 .또는 \n나왔을 때 먼저 cnt를 4로 나눈 몫 x 4 만큼 replace() 함수를 이용해 X를 A로 변경시켜주고 나머지 X는 B로 변경시켜주었다. 이때 cnt의 개수가 2의 배수가 아니면 X를 A 또는 B로 바꿀 수 없기에 -1을 출력해 주는 방법으로 풀었다.

두 번째 풀이는 단순하게 board의 XXXX를 AAAA로 먼저 replace() 함수를 이용해 변경해주고 XX를 BB로 변경해 주었다. 만약 교체를 해준 후에도 X가 남아있으면 -1을 출력해 주는 방법으로 풀었다.

🛠 풀이 1

import sys
input = sys.stdin.readline

def sol(board):
    cnt = 0

    for idx, val in enumerate(board):
        if val == 'X':
            cnt += 1
        else:
            if cnt == 0:
                continue
            else:
                if cnt % 2 == 0:
                    board = board[:idx].replace('X', 'A', 4 * (cnt//4)) + board[idx:]
                    board = board[:idx].replace('X', 'B') + board[idx:]
                    cnt = 0
                else:
                    return -1

    return board

if __name__ == '__main__':
    board = input()

    print(sol(board))

🛠 풀이 2

import sys
input = sys.stdin.readline

def sol(board):
    board = board.replace('XXXX', 'AAAA')
    board = board.replace('XX', 'BB')

    if board.count('X') != 0:
        return -1
    else:
        return board

if __name__ == '__main__':
    board = input()

    print(sol(board))

✔️ 정리

이번 문제는 아주 어렵지 않았다. 첫 번째 풀이는 시간 복잡도는 O(N³)이기 때문에 시간제한이 1초였다면 시간 초과로 오답 처리가 되었을 것이기에 조금 더 생각해 두 번째 풀이로 문제를 해결해 보았다. 두 번째 풀이는 시간 복잡도는 O(N²)이다.

⚡직접 문제를 풀어보고 작성한 글입니다.⚡
🙂틀린 부분이나 보완할 점이 있을 경우 언제든지 댓글 혹은 메일로 지적해 주시면 감사하겠습니다!🙂