https://www.acmicpc.net/problem/1343
시간 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
2 초 | 128 MB | 12349 | 6585 | 5572 | 53.224% |
문제
민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB
이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.
출력
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
문제 풀이
처음 풀었을 때 굉장히 헷갈렸다. 여러 번 시도를 하였고 난이도에 비해 생각보다 매우 힘겹게 풀었다.
내가 시도하였다가 실패한 방법들도 기재하겠다.
1. StringTokenizer
StringTokenizer을 사용하여 .을 만났을 때를 기준으로 나눠야 하나? 라는 생각으로 시도하였으나, 나누는 것은 할 수 있지만 .과 함께 출력해야 하므로 안된다고 결론을 내었다.
2. Stack
예전에 이와 유사한 문제를 Stack을 사용하여 풀었던 경험이 있다. 따라서 문자가 X일 때 스택에 넣고, .일 때 스택에서 있는 것들을 빼내서 출력하고 마지막에 .을 붙이는 방식으로 코드를 구현하였으나, 점이 없는 부분의 출력을 어떻게 구현하는지 몰라서 많이 고생하다가 좋지 않은 로직이라는 판단하에 다른 풀이 방법으로 변경하였다.
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next(); // 사용자로부터 폴리오미노 문자열을 입력받음
sc.close(); // 스캐너를 닫음
String res = "";
res = poliomino(s); // 폴리오미노 변환 함수 호출
System.out.println(res); // 결과 출력
}
// 주어진 폴리오미노 문자열을 변환하는 함수
private static String poliomino(String s) {
Stack<Character> stack = new Stack<>(); // 스택 생성
StringBuilder ansBuilder = new StringBuilder(); // 변환된 결과를 저장할 StringBuilder
String A = "AAAA", B = "BB"; // 변환 규칙에 따른 문자열 상수 정의
for (char c : s.toCharArray()) {
if (c == 'X') {
stack.push(c); // 'X' 문자일 경우 스택에 추가
} else if (c == '.') {
if (stack.size() % 2 != 0) {
return "-1"; // 스택에 남은 요소가 홀수면 변환 실패
}
while (!stack.isEmpty()) {
if (stack.size() >= 4) {
ansBuilder.append(A); // 'AAAA' 추가
stack.pop();
stack.pop();
stack.pop();
stack.pop();
} else {
ansBuilder.append(B); // 'BB' 추가
stack.pop();
stack.pop();
}
}
ansBuilder.append('.'); // '.' 추가
}
}
return ansBuilder.toString(); // 최종 결과 반환
}
}
입력: XX.XXXXXXXXXX..XXXXXXXX...XXXXXX
출력: BB.AAAAAAAABB..AAAAAAAA...
이런 식으로 마지막 부분이 출력되지 않는다.
정답 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next(); // 사용자로부터 폴리오미노 문자열을 입력받음
sc.close(); // 스캐너를 닫음
String answer = "";
answer = poliomino(s); // 폴리오미노 변환 함수 호출
System.out.println(answer); // 결과 출력
}
// 주어진 폴리오미노 문자열을 변환하는 함수
private static String poliomino(String s) {
String ans = ""; // 변환된 결과를 저장할 문자열
String A = "AAAA", B = "BB"; // 변환 규칙에 따른 문자열 상수 정의
// 문자열에서 "XXXX" 패턴을 "AAAA"로 대체하여 A를 채움
s = s.replaceAll("XXXX", A);
// 문자열에서 "XX" 패턴을 "BB"로 대체하여 B를 채움
ans = s.replaceAll("XX", B);
// 변환된 문자열에 'X' 문자가 남아있다면 폴리오미노 변환 실패
if (ans.contains("X")) {
ans = "-1"; // 결과를 -1로 설정
}
return ans; // 최종 결과 반환
}
}
그리디 알고리즘에 대한 공부가 아직 부족하다는 것을 느꼈다.
- "XXXX" 패턴을 "AAAA"로 대체하고 "XX" 패턴을 "BB"로 대체하여 문자열을 변환
- 변환된 문자열에 'X' 문자가 남아있다면, 폴리오미노 변환 실패로 -1을 반환
이런 순서로 문제풀이를 진행하였다.
'Algorithm > baekjoon' 카테고리의 다른 글
[백준 1002/자바(java)] 터렛 (0) | 2023.08.21 |
---|---|
[백준 1380/자바(java)] 귀걸이 (0) | 2023.08.20 |
[백준 16194/자바(java)] 카드 구매하기 2 (0) | 2023.08.16 |
[백준 24445/자바(java)] 알고리즘 수업 - 너비 우선 탐색 2 (0) | 2023.08.15 |
[백준 10799/자바(java)] 쇠막대기 (0) | 2023.08.11 |