1. 문제 조건
2. 아이디어
주어진 시간은 2초이다.
S의 길이는 최소 1에서 최대 999, T의 길이는 최대 1000이다. S에서 T가 만들어질 수 있는 지 확인하기 위해 문자열 뒤에 A을 한 번 추가해보고, 또 문자열을 뒤집고 B를 추가하는 연산을 각각 수행해보는 완전탐색 방식은 시간초과가 난다.
S의 길이가 1이고 T의 길이가 1000인 최악의 상황을 고려했을 때, 999자리만큼 문자를 늘려야한다. 위에서 설명한 방식은 한 자리씩 늘릴 때마다 2가지 경우의 수가 존재하므로 2의 999제곱이 되어 시간초과가 발생한다. 따라서 S에서 완전탐색으로 T를 만들어나가는 과정은 적용할 수 없다.
그렇다면 반대로 T에서 S를 만들어나가면 된다.
S에 1번 연산을 적용하면 맨 뒤 알파벳은 A가 되고 2번 연산을 적용하면 맨 뒤 알파벳이 B가 된다. 따라서 T는 맨 뒤 알파벳만 보고 1번과 2번중 어떤 연산이 적용된 결과인 지 알 수 있으니, 한 번만 역연산을 취하면 된다.
따라서 역연산을 S와 T의 길이가 같지 않을 때까지 반복한 후, 길이가 같아지는 순간 두 문자열이 동일한지 확인하면 S를 T로 만들 수 있는지의 여부를 알아낼 수 있다.
3. 구현
우선 StringBuffer를 사용해서 문자열을 뒤집는 방식을 택해 구현했다.
package gold5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.Stream;
public class Main_12905a와b {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static String S, T;
public static void main(String[] args) throws IOException {
input();
System.out.println(pro(S, T));
}
public static int pro(String original, String target) {
while (original.length()<target.length()) {
//문자열 맨 뒤가 A이면 A 떼기
if (target.charAt(target.length() - 1) == 'A') {
target = target.substring(0, target.length() - 1);
} else {
//문자열 맨 뒤가 B면 떼고 뒤집기
target = target.substring(0, target.length() - 1);
target = reverse(target);
}
}
if(target.equals(original)) return 1;
else return 0;
}
public static String reverse(String str) {
StringBuffer sb = new StringBuffer(str);
return sb.reverse().toString();
}
public static void input() throws IOException {
S = br.readLine();
T = br.readLine();
}
}
문제 풀이 이후 다른 사람들의 풀이를 살펴보니 StringBuilder를 이용해 아래와 같이 문자열을 뒤집는 방식도 있다는 것을 알았다. 이 방법을 적용하면 맨 뒤 알파벳을 지우는 것도, 문자열을 뒤집는 것도 훨씬 간편하게 구현이 가능했다. 다음에 문자열 뒤집는 풀이가 필요할 때 적용해봐야겠다!
public static int pro(String original, String target) {
StringBuilder t = new StringBuilder(target);
while (original.length()<t.length()) {
//문자열 맨 뒤가 A이면 A 떼기
if (t.charAt(t.length() - 1) == 'A') {
t.deleteCharAt(t.length()-1);
} else {
//문자열 맨 뒤가 B면 떼고 뒤집기
t.deleteCharAt(t.length()-1);
t.reverse();
}
}
if(t.toString().equals(original)) return 1;
else return 0;
}
'Learning-log > Algorithm 문풀' 카테고리의 다른 글
백준 17135번 캐슬 디펜스 (Python) (0) | 2024.08.07 |
---|---|
(Python) 백준 2164번 카드2 (0) | 2024.07.20 |
백준 1240번. 노드사이의 거리 (Java) (0) | 2024.02.16 |
백준 2579번 계단 오르기(Java) (0) | 2023.10.01 |
백준 17182번 우주탐사(JAVA) (1) | 2023.09.30 |