[BOJ]12904-A와 B(G5)

문제

12904 - A와 B

---

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

---

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력

---

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

문제 풀이

---

방법이 몇 개인지를 구하는게 아니라 바꿀 수 있는지 유무를 판단하는 문제임을 생각해야한다.

1. S → T
   두 가지 방법을 모두 고려해서 확인해야함

1. T → S
   맨 뒷자리가 A인지 B인지만 확인하면 방법이 정해짐

if (c == 'A') {
			t.deleteCharAt(t.length() - 1);
} else {
			t.deleteCharAt(t.length() - 1);
			t.reverse();
}

전체코드

1. String으로 입력받아서 reverse 메서드를 직접 구현하는 방식
   String은 불변객체이기 때문에 +연산을 하는 경우 객체에 값을 변경하는것이 아니라, 새로운 객체를 생성해서 참조하는 것이기 때문이다.

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		String t = br.readLine();

		while (t.length() > s.length()) {
			char c = t.charAt(t.length() - 1);
			if (c == 'A') {
				t = t.substring(0, t.length() - 1);
			} else {
				t = t.substring(0, t.length() - 1);
				t = reverse(t);
			}
		}
		System.out.println(s.equals(t) ? 1 : 0);
	}

	static String reverse(String s) {
		String answer = "";
		for (int i = s.length() - 1; i >= 0; i--) {
			answer += s.charAt(i);
		}
		return answer;
	}
}

2. StringBuilder로 입력받아서 내장 메서드 reverse()를 이용하는 방식

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder s = new StringBuilder(br.readLine());
		StringBuilder t = new StringBuilder(br.readLine());

		while (t.length() > s.length()) {
			char c = t.charAt(t.length() - 1);
			if (c == 'A') {
				t.deleteCharAt(t.length() - 1);
			} else {
				t.deleteCharAt(t.length() - 1);
				t.reverse();
			}
		}
		System.out.println(s.toString().equals(t.toString()) ? 1 : 0);
	}
}

메모리, 시간적으로 너무나도 차이가 많았습니다…

💡 String vs StringBuilder

---

String

String은 불변 객체로서 한 번 생성되면 변경할 수 없다. 만약 아래의 연산을 진행하는 경우 결과값마다 새로운 문자열 객체가 생성된다. 연산을 진행할 때마다 메모리 할당과 결국을 메모리 해제까지 진행되기 때문에 연산이 많아질 수록 성능적으로 좋지 않다.

String a = "Hello ";
String b = "World";
String c = a + b;

System.out.println(c);	// Hello World

StringBuilder

StringBuilder는 String과 다르게 새로운 객체 생성이 아닌 이전의 객체를 변경하는 방식을 사용하기 때문에 부하가 적고 메모리와 시간적으로 String에 비해 우세하다.

StringBuffer의 경우에도 유사하게 동작하지만 Thread-Safe 여부가 다르다. StringBuffer는 thread-safe하기 때문에 여러 쓰레드에서 동일한 문자열에 접근하는 경우 주로 사용한다. 하지만 이런 경우가 아닌 경우에는 StringBuilder가 StringBuffer에 비해 성능적으로 우세하다.

StringBuilder a = new StringBuilder("Hello ");
StringBuilder b = new StringBuilder("World");
StringBuilder c = new StringBuilder(a.append(b));
		
System.out.println(c);	// Hello World