BaekJoon 1593번: 문자 해독(C++)

www.acmicpc.net/problem/1593

1593번: 문자 해독

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

ascii 코드를 이용하여 배열을 만든다면 풀 수 있는 문제이나, 시간초과 같은 문제로 인해 난이도가 높다.

 

Google 등에 풀이 자료가 많지 않은 문제이기에, 문제를 풀다가 막혔던 분들은 맨 밑으로 내려서 주의사항을 읽는 것을 추천한다. (필자는 총 8번의 시간초과를 통해 문제를 풀었기에, 아주 조금이나마 같은 문제를 겪는 분들에게 도움을 주고자 참고사항에 막힐만한 부분을 적어두었다.)

 

 

풀이법

1) W의 값을 소문자와 대문자로 나누어서 배열에 저장한다.

2) 처음에는 S의 값을 W의 크기만큼 잘라서 소문자와 대문자로 나누어 저장한다.

3) 시간 초과를 고려하여 S값 중 가장 작은 index에 해당하는 부분을 삭제하고, 새로운 index를 추가 하는 방식으로 계산의 횟수를 최대한 줄인다.  

#include <iostream>
#include<string>
#include<vector>
#include <cstring>
#include<algorithm>
using namespace std;

int g, s;
string w;
string S;
int ans = 0;
int wminArr[27];
int wmaxArr[27];
int sminArr[27];
int smaxArr[27];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> g >> s;
	cin >> w;
	for (int i = 0; i < g; i++)
	{
		if (w[i] >= 'a' && w[i] <= 'z')
			wminArr[(int)(w[i] - 'a')]++;
		else
			wmaxArr[(int)(w[i] - 'A')]++;

	}

	cin >> S;

	for (int i = 0; i < s; i++)
	{
		if (i < g)
		{
			if (S[i] >= 'a' && S[i] <= 'z')
				sminArr[(int)(S[i] - 'a')]++;
			else
				smaxArr[(int)(S[i] - 'A')]++;
		}
		else
		{
			if (S[i - g] >= 'a' && S[i - g] <= 'z')
				sminArr[(int)(S[i - g] - 'a')]--;
			else
				smaxArr[(int)(S[i - g] - 'A')]--;


			if (S[i] >= 'a' && S[i] <= 'z')
				sminArr[(int)(S[i] - 'a')]++;
			else
				smaxArr[(int)(S[i] - 'A')]++;
		}
		bool check = true;
		for (int j = 0; j < 27; j++)
		{
			if (sminArr[j] != wminArr[j] || smaxArr[j] !=wmaxArr[j])
			{
				check = false;
				break;
			}
		}
		if (check == true)
		{
			ans++;
		}
	}
	cout << ans;
}

참고사항)

- 아스키 코드까지 고려했다면, 시간이 넉넉할 경우 충분히 문제를 풀 수 있었을 것이다

(아래의 방식들은 직접 다 시도했던 방식들이다)

 

- 아스키 코드의 합과 같은 방식으로는 문제를 해결할 수 없다. (a+d = b+c) 인 것을 고려하자

 

- substr함수로 문자열를 직접 잘라 돌리는 경우 시간 초과에 직면할 가능성이 크다. 중복되는 계산이 많아진 다는 점을 고려 해야 한다.

substr을 사용 시 0~4 / 1~5 두번을 계산하면, 1 2 3 4 원소에 접근이 두번 필요하다.

허나 배열을 이용한다면, 0~4 / 1~5 계산 시 0번 index의 값을 빼고, 5번 index의 값을 넣어주는

두번의 연산으로 문제의 복잡도를 낮출 수 있다.

 

- 필자와 달리 소문자 배열, 대문자 배열을 나누지 않고 푸는 방법 또한 존재한다. 실제 Ascii코드에서는 A가 a보다 작은 값을 가지기에 (int)(S[i] - 'A') 와 같은 방식을 사용하여 겹치지 않게 배열의 index를 잡을 수 있다. 

이 경우에는 배열의 크기를 알파벳의 개수(소문자 26, 대문자 26)인 52보다는 꼭 크게 잡도록 해야 한다.

실제 Ascii코드 표를 보면 'Z'와 'a'사이에 5개의 문자들이 들어가 있다. (outOfBound 뜨시는 분들은 여길 참고)

 

문제를 푸는데 도움이 되었기를 바래보며 글은 마친다.