이번 문제는 아이디어만 떠오르면 매우 간단한 문제입니다.
1. 오늘의 학습 키워드
- 그리디
2. 문제: 1343. 폴리오미노
- 단계: 🥈 실버 5단계
- 주제:
- 출처: https://www.acmicpc.net/problem/1343
문제
민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB
이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.
출력
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
예제 입력 1 복사
XXXXXX
예제 출력 1 복사
AAAABB
예제 입력 2 복사
XX.XX
예제 출력 2 복사
BB.BB
예제 입력 3 복사
XXXX....XXX.....XX
예제 출력 3 복사
-1
예제 입력 4 복사
X
예제 출력 4 복사
-1
예제 입력 5 복사
XX.XXXXXXXXXX..XXXXXXXX...XXXXXX
예제 출력 5 복사
BB.AAAAAAAABB..AAAAAAAA...AAAABB
3. 문제 풀이
Step1. 문제 이해하기
주어진 문제는 두 개의 폴리오미노 AAAA, BB 가 있다고 합니다.
‘.’와 ‘X’로 이루어진 보드판이 주어졌을 때, ‘X’를 모두 폴리오미노로 덮으려고 합니다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하는게 이 문제입니다.
입출력을 살펴보도록 하겠습니다.
- Input:
- 첫째 줄에 보드판이 주어집니다. 보드판의 크기는 최대 50입니다.
- Output: 첫째 줄에 사전순으로 가장 앞서는 답을 출력합니다. 만약 덮을 수 없다면 -1을 출력합니다.
Step2. 문제 분석하기
AAAA 의 길이는 4, BB 의 길이는 2입니다.
즉, AAAA는 4개의 연속적으로 이뤄진 X를 변경할 수 있고, BB는 2개의 연속적으로 이뤄진 X를 변경할 수 있습니다.
이 방법이 최선의 방법이며, 전체적인 결과를 도출하는데도 최선입니다.
따라서, 해당 문제는 그리디 유형의 문제이며, 위와 같이 구현하면 금방 해결할 수 있는 문제입니다.
Step3. 코드 설계
- replace 메서드를 사용하여 ‘XXXX’를 ‘AAAA’로, ‘XX’를 ‘BB’로 변경합니다.
Step4. 코드 구현
import sys
boards = sys.stdin.readline().strip()
boards = boards.replace('XXXX', 'AAAA').replace('XX', 'BB')
print(-1 if 'X' in boards else boards)- 시간 복잡도: boards의 길이인 N만큼의 시간복잡도가 나옵니다,
- 결과:
4. 마무리
이번 문제는 바꾸고자 하는 문자열의 길이에 맞는 폴리오미노를 선택하는 행위가 최선의 행위인 그리디 유형의 문제였습니다.
글 읽어주셔서 감사합니다.
