[G3] 백준 23084번 IUPC와 비밀번호 C++ 문자열, 슬라이딩 윈도우

리뷰

 

https://www.acmicpc.net/problem/23084

암호화 조건을 반대로 생각해서 복호화 하는 논리적으로 접근하기 좋은 문제

 

 

전역 변수

• s, t : 비밀번호와 비밀번호 후보 문자열을 저장할 변수
• n : 후보 문자열이 주어지는 횟수를 저장할 변수
• sl, tl : 비밀번호와 비밀번호 후보 문자열의 길이를 저장할 변수
• sc : 비밀번호의 문자 개수를 저장할 배열
• tc : 비밀번호 후보의 문자 개수를 저장할 배열

 

함수

1. chk

bool chk()

 

비밀번호와 현재 완성된 비밀번호 후보의 개수 차이를 체크할 함수

1. 변수 diff를 0으로 초기화 하고, 각 문자의 개수 차이를 diff에 더해준다.
2. diff의 차이가 2를 초과한 경우 false를, 아닌 경우 true를 리턴해 준다.

 

문제풀이

1. s, n값을 입력 받고, sl을 s의 크기로 저장해 준다.
2. s를 순회하며 s를 구성하는 각 문자의 개수를 sc배열에 저장해 준다.
3. n번의 while 루프를 수행하고, 매 루프마다 비밀번호 후보 t를 입력 받아준다.
4. tl에 t의 크기를 저장해 주고, 만약 tl이 sl 보다 작다면 바로 NO를 출력 후 continue 처리해 준다.
5. 만약 tl과 sl이 같은 경우 두 문자열을 정렬하고, 문자열이 동일한 경우 NO를 출력 후 continue 처리해 준다.
6. memset 메서드를 통해 tc의 값을 0으로 초기화 하고, 문자 타입 덱 deq를 초기화 해준다.
7. 먼저 t의 sl개의문자를 deq에 삽입해 주고, 각 문자의 개수를 tc배열에 저장해 준다.
8. chk함수를 호출해 true를 반환 받았다면 YES를 출력하고 continue처리해 준다.
9. 변수 flag의 초깃값을 false로 초기화 해주고, sl ~ tl - 1까지의 for문을 개행해 준다.
10. deq의 front인 문자의 개수를 줄여준 후 pop_front로 deq에서 제외해 준다.
11. 현재 문자의 개수를 증가시킨 후 push_back으로 deq에 추가해 준다.
12. chk함수를 호출하고 true를 반환 받았다면 flag를 true로 바꾼 후 break처리해 준다.
13. 모든 탐색을 마친 후 flag가 true라면 YES를, 아니라면 NO를 출력해 준다.

 

트러블 슈팅

1. 슬라이딩 윈도우의 문자열과 s를 비교하는 것에 있어 어려움이 있었다.
2. 결국 모든 문자를 비교하되 diff가 2보다 커질 경우 조기 종료해 주는 것으로 설정하니 AC를 받았다.

 

참고 사항

• s와 t의 길이가 같으면서 문자의 개수가 완전히 동일하다면 마지막으로 임의의 위치에 있는 문자 1개를 골라 다른 문자로 바꾼다. 라는 조건에 위배되게 된다.

 

정답 코드

#include<iostream>
#include<cstring>
#include<deque>
#include<algorithm>
using namespace std;

string s, t;
int n, sl, tl;
int sc['z' + 1];
int tc['z' + 1];

bool chk() {
	int diff = 0;
	for (int i = 'a'; i <= 'z'; ++i) {
		diff += abs(sc[i] - tc[i]);
		if (diff > 2) return false;
	}
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> s >> n;
	sl = s.size();
	for (char ch : s) sc[ch]++;
	while (n--) {
		cin >> t;
		tl = t.size();
		if (tl < sl) {
			cout << "NO\n";
			continue;
		}
		else if (tl == sl) {
			string temp1 = s;
			string temp2 = t;
			sort(temp1.begin(), temp1.end());
			sort(temp2.begin(), temp2.end());
			if (temp1 == temp2) {
				cout << "NO\n";
				continue;
			}
		}
		memset(tc, 0, sizeof(tc));
		deque<char> deq;
		for (int i = 0; i < sl; ++i) {
			deq.push_back(t[i]);
			tc[t[i]]++;
		}
		if (chk()) {
			cout << "YES\n";
			continue;
		}

		bool flag = false;
		for (int i = sl; i < tl; ++i) {
			tc[deq.front()]--;
			deq.pop_front();
			tc[t[i]]++;
			deq.push_back(t[i]);
			
			if (chk()) {
				flag = true;
				break;
			}
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
}