[백준] 12919번: A와 B 2
📝문제
다양한 방법을 시도해봤다.
이 문제를 풀 때 조심해야 할 것은 s부터 출발하여 t를 만드는 완전탐색의 방법을 택하면 시간초과나 메모리초과가 발생한다는 것이다.
시간복잡도가 O(2^n)이기 때문에...
따라서 t에서 출발하여 주어진 조건에 따라 문자를 삭제해가며 s가 나올 수 있는지 탐색해야한다.
이렇게 한다며 불필요한 경우의 수를 제거할 수 있다.
📌코드
package Solving;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ12919 {
/**
* 두가지 경우를 recursive하게 탐색 -> 시간초과
* 1. StringBuilder를 이용한 reverse()는 시간초과
* 2. for문을 활용한 뒤집기는 시간초과
*
* BFS를 사용하여 탐색 -> 메모리초과
*
* t에서 주어진 경우에 따라 문자열을 제거하면서(재귀) s가 나오는지 확인
*
*/
static boolean answer = false;
static StringBuilder sb;
static void recur(String s, String t){
// stop condition
if(s.equals(t)) {
answer = true;
return;
}
if(s.length() >= t.length()) return;
// t의 끝자리가 A인 경우
if(t.charAt(t.length()-1) == 'A'){
recur(s, t.substring(0, t.length()-1));
}
// t의 첫번째 글자가 B인 경우
String temp = "";
if(t.charAt(0) == 'B'){
// 뒤집고 B를 제거
sb = new StringBuilder(t);
temp = sb.reverse().toString().substring(0, t.length()-1);
recur(s, temp);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
String t = br.readLine();
recur(s, t);
System.out.println(answer ? 1 : 0);
}
}
Author And Source
이 문제에 관하여([백준] 12919번: A와 B 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@paulus0617/boj12919
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
package Solving;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ12919 {
/**
* 두가지 경우를 recursive하게 탐색 -> 시간초과
* 1. StringBuilder를 이용한 reverse()는 시간초과
* 2. for문을 활용한 뒤집기는 시간초과
*
* BFS를 사용하여 탐색 -> 메모리초과
*
* t에서 주어진 경우에 따라 문자열을 제거하면서(재귀) s가 나오는지 확인
*
*/
static boolean answer = false;
static StringBuilder sb;
static void recur(String s, String t){
// stop condition
if(s.equals(t)) {
answer = true;
return;
}
if(s.length() >= t.length()) return;
// t의 끝자리가 A인 경우
if(t.charAt(t.length()-1) == 'A'){
recur(s, t.substring(0, t.length()-1));
}
// t의 첫번째 글자가 B인 경우
String temp = "";
if(t.charAt(0) == 'B'){
// 뒤집고 B를 제거
sb = new StringBuilder(t);
temp = sb.reverse().toString().substring(0, t.length()-1);
recur(s, temp);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
String t = br.readLine();
recur(s, t);
System.out.println(answer ? 1 : 0);
}
}
Author And Source
이 문제에 관하여([백준] 12919번: A와 B 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@paulus0617/boj12919저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)