백준 - A와B2

문제 설명

A⇒ B로 바꿀수 있는지 가능여부를 물어보는 문제이다.

주의사항

• 완전탐색 시간복잡도를 측정해봐야한다.
• 50의 길이

시도

• 완전탐색 FAIL
• 백트래킹만들어질 수 없는 경우는 탐색하지 않도록 한다.
• 일반 완전탐색은 2^50까지 나온다.

풀이 - [덱을 이용한 풀이]

문자를 추가하는 것은 괜찮다 하지만 뒤집고 뒤집고 .. 이런행위가 시간초과에 영향을 줄 수 있다고 생각했기 때문에 사용하지 않았다.

static boolean isPossible = false;

	public static boolean isChange(String A, String B) {
		LinkedList<Character> results = new LinkedList<>();

		for (char c : A.toCharArray()) {
			results.offerLast(c);
		}

		tryAToB(B, results, true);

		return isPossible;
	}

	/**
	 * 아이디어가 완전탐색밖에 생각안남 2^50. 14% TLE
	 * 무조건 마지막에 넣는 것이 아니라 이제는 앞으로 넣어줘야 한다.
	 */
	public static void tryAToB(String B, LinkedList<Character> result, boolean isStartFront) {
		if (isPossible || result.size() > B.length()) {
			return;
		}

		if (!isSimilar(B, result, isStartFront)) {
			return;
		}

		if (result.size() == B.length()) {

			if (isStartFront && isSame(B, result)) {
				isPossible = true;
			} else if (!isStartFront && isSameForTail(B, result)) {
				isPossible = true;
			}

			return;
		}

		if (isStartFront) {
			result.offerLast('A');
		} else {
			result.offerFirst('A');
		}
		tryAToB(B, result, isStartFront);
		if (isStartFront) {
			result.pollLast();
		} else {
			result.pollFirst();
		}

		if (isStartFront) {
			result.offerLast('B');
		} else {
			result.offerFirst('B');
		}
		tryAToB(B, result, !isStartFront);
		if (isStartFront) {
			result.pollLast();
		} else {
			result.pollFirst();
		}
	}

	/**
	 * 백트래킹 핵심 포인트
	 */
	public static boolean isSimilar(String B, LinkedList<Character> result, boolean isFrontStart) {
		StringBuilder sb = new StringBuilder();
		result.forEach(sb::append);

		return B.contains(sb.toString()) || B.contains(sb.reverse().toString());
	}

	private static boolean isSameForTail(String B, LinkedList<Character> result) {
		int n = result.size();
		for (int i = result.size() - 1; i >= 0; i--) {
			if (B.charAt(n - 1 - i) != result.get(i)) {
				return false;
			}
		}

		return true;
	}

	private static boolean isSame(String B, LinkedList<Character> result) {
		for (int i = 0; i < result.size(); i++) {
			if (B.charAt(i) != result.get(i)) {
				return false;
			}
		}

		return true;
	}