[백준] 12904번 문제풀이

문제 : www.acmicpc.net/problem/12904

12904번: A와 B

 

알고리즘 :

1. T의 마지막이 A이면 A를 삭제

2. T의 마지막이 B이면 B를 삭제 후 뒤집기

3. T와 L의 Length가 일치하거나, T의 Length가 더 작아지면 종료

 

S를 가지고 T를 만들어 나가지 말고,

T를 가지고 조건을 통해 삭제를 해나가다가, S의 크기와 같거나, 작아지면 서로 일치한 지 확인하면 된다.

 

기존에는, S와 T가 서로 일치한지 T가 한 번 바뀔 때마다 확인했었는데, 그렇게 하면 시간 초과될 것 같아서,

고민을 하다가 S와 T의 크기가 일치할 때만 문자가 일치한지 확인하면 되는 걸 찾았다. 완전 유레카였다.

 

소스코드 :

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_LENGTH 1001

void reverse(char* arr, int len)
{
	for (int i = 0; i < (len / 2) + 1; i++)
	{
		char temp = arr[len - i];
		arr[len - i] = arr[i];
		arr[i] = temp;
	}
}

int equal(char* arr1, char* arr2)
{
	for (int i = 0; arr1[i] != '\0'; i++)
	{
		if (arr1[i] != arr2[i]) { return 0; }
	}
	return 1;
}

int main(void)
{
//while(1){
	char S[MAX_LENGTH];
	char T[MAX_LENGTH];
	scanf("%s", S);
	scanf("%s", T);

	int s_len = 0;
	int t_len = 0;
	for (int i = 0; S[i] != '\0'; i++) { s_len++; }
	for (int i = 0; T[i] != '\0'; i++) { t_len++; }

	while (s_len < t_len)
	{
		if (T[--t_len] == 'A')
		{
			T[t_len] = '\0';
		}
		else
		{
			T[t_len] = '\0';
			reverse(T, t_len - 1);
		}
		//printf("%s\n", T);
	}

	printf("%d\n", equal(S, T));
//}

	return 0;
}

한 번 확인이나 해볼까? 라는 상태에서 제출한 코드라 디버깅할 때 쓰이던 문장들이 주석처리되어있다.

 

테스트 케이스 :

B
ABBA

AB
ABB

ABB
ABB

AA
AAABA

AB
BABAB

BA
BABAB

 

걸린 시간: 86분 (알고리즘 : 11분, 구현 및 디버깅 75분)

위에서 얘기한 어떤 조건일 때 비교를 할 것인가? 에서 시간을 많이 잡아먹었다.