12919번: A와 B 2
수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈
www.acmicpc.net
- 풀이
bfs 방식을 사용했습니다.
1. 큐에서 나온 문자열이 S와 같은 경우 : answer을 1로 초기화한 후 bfs 종료합니다.
2. 맨 앞에 B가 있는 경우 : 이전에 3번을 적용해서 B를 추가하고 뒤집었다는 뜻으로 반대로 맨 앞을 없애고 뒤집어서 큐에 넣어줍니다.
3. 맨 뒤에 A가 있는 경우 : 이전에 2번을 적용해서 A를 추가 했다는 소리이므로 A를 없애고 큐에 넣어줍니다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static int answer;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
String S = in.nextLine();
String T = in.nextLine();
Queue<String> queue = new LinkedList<>();
answer = 0;
queue.add(T);
while (!queue.isEmpty()) {
String temp = queue.poll();
if(temp.equals(S))
{
answer = 1;
break;
}
if(temp.length() >= 2 &&temp.charAt(0) == 'B')
{
queue.add(new StringBuilder(temp.substring(1)).reverse().toString());
}
if(temp.length() >= 2 && temp.charAt(temp.length() - 1) == 'A')
{
queue.add(temp.substring(0,temp.length()-1));
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 1561번 : 놀이 공원 (0) | 2022.01.19 |
|---|---|
| [BOJ/JAVA] 백준 16930번 : 달리기 (0) | 2022.01.17 |
| [BOJ/JAVA] 백준 20207번 : 달력 (0) | 2021.11.21 |
| [BOJ/JAVA] 백준 1706번 : 크로스워드 (0) | 2021.11.19 |
| [BOJ/JAVA] 백준 11497번 : 통나무 건너뛰기 (0) | 2021.11.09 |
