문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23 <- 여기를 참고해주세요!
https://www.acmicpc.net/problem/12919
12919번: A와 B 2
수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈
www.acmicpc.net
https://nodingco.tistory.com/30 의 시리즈 문제입니다.
1. 이해 (5분) - 1분
A와 B 문제와 언뜻 보면 똑같아보이는 문제입니다.
하지만 조금 생각해보면 풀이를 위한 접근 방식이 전혀 다른걸 알 수 있습니다.
앞의 문제에선 연산을 통한 결과가 맨 뒤 알파벳으로 나타나서 역순으로 따라가기만 하면 문제의 풀이가 가능하지만, 해당 문제에선 알파벳을 먼저 붙이고 뒤집기 때문에 맨 뒤 알파벳이 어떤 연산을 통해 나온 것인지 여러 경우가 생깁니다.
대신 문자열의 형태를 보고 어느정도 경우를 좁힐 수 있고 문자열의 길이도 앞 문제보다 훨씬 작습니다.
2. 계획 (5분) - 3분
재귀를 통해 뒷 문자열을 만들기 위해 가능한 경우를 역으로 되짚어갑니다.
대신 두가지 경우를 매 번 탐색하는게 아니라, 맨 뒷 문자가 A거나 맨 앞 문자가 B일때만 탐색합니다.
(1번 연산이 진행되면 문자열의 맨 뒤는 무조건 A, 2번 연산이 진행되면 맨 앞이 무조건 B)
그렇게 줄인 문자열의 길이가 앞의 문자열과 같아지면 두 문자열이 같은지, 즉 문제의 조건이 가능한지를 체크하고 그 결과를 저장합니다. 이때 True False에 따라 재귀문을 끝내는 조건을 움직여서 가능여부가 한 번 찾아지면 덮어씌워지지 않게했습니다.
3. 검증 (5분) - 1분
검증내용은 A와B 1번 문제와 유사하기때문에 패스하겠습니다.
4. 풀이 (30분) - 17분
재귀문 구현 부분은 조금 신경썼지만, 문자열을 조정하는 부분은 오히려 앞 문제보다 쉽게 구현 할 수 있었습니다.
5. 채점, 디버깅
다행히 이번에도 한 번에 통과했습니다. 감사합니다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N;
static char[] S;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
S = br.readLine().toCharArray();
char[] T = br.readLine().toCharArray();
N = S.length;
makeS(T, T.length);
if (N == 100) {
System.out.println(1);
} else {
System.out.println(0);
}
}
static void makeS(char[] T, int l) {
if (l < N) {
return;
}
if (l == N) {
N = (checkS(T)) ? 100 : N;
return;
}
if (T[l - 1] == 'A') {
char[] newT = new char[l - 1];
for (int i = 0; i < l - 1; i++) {
newT[i] = T[i];
}
makeS(newT, l - 1);
}
if (T[0] == 'B') {
char[] newT = new char[l - 1];
for (int i = 0; i < l - 1; i++) {
newT[i] = T[l - 1 - i];
}
makeS(newT, l - 1);
}
}
static boolean checkS(char[] T) {
for (int n = 0; n < N; n++) {
if (T[n] != S[n]) {
return false;
}
}
return true;
}
}
'🔍 알고리즘 > 백준 Java' 카테고리의 다른 글
| [Java] 백준 1562번. 계단수 (골드1) (0) | 2022.07.22 |
|---|---|
| [Java] 백준 1194번. 달이 차오른다, 가자 (골드1) (0) | 2022.07.21 |
| [Java] 백준 12904번. A와B (골드5) (0) | 2022.01.25 |
| [Java] 백준 15810번. 풍선공장 (실버2) (0) | 2022.01.13 |
| [Java] 백준 18858번. 훈련소로 가는 날 (골드3) (0) | 2022.01.10 |
