32073 c++ XOR 최대

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

 

이진수로 이루어진 문자열 s가 주어질 때, 해당 수의 부분문자열 s1, s2을 XOR 연산한 값 중에서 최댓값을 구해야 하는 문제이다.

 

우선 가장 중요한 관찰은 가장 왼쪽에 있는 비트가 1이어야 하기 때문에 두 부분 문자열 중에서 한개는 반드시 그 문자열 자체라는 것. 그리고 해당 문자열의 길이와 가장 왼쪽에 있는 1의 위치가 일치하지 않을 수도 있기 때문에 시작점을 찾아줘야 한다는 것.

 

그리고 가장 핵심적인 관찰! 

원래 문자열에서 1이 처음 시작된 시점부터 끝나는 지점까지를 s-e라고 했을 때, 그 후 0이 연속적으로 나오는 부분이 있을 것이다.

우리는 이 부분을 1로 만들면 된다.

그리고, 0이 연속적으로 나오는 것의 길이를 l이라고 했을 때, l개 이상의 1을 갖고 있는 문자열과 XOR 한다면 숫자가 더 작아져 버린다.

 

때문에, greedy 하게 생각하면, 길이가 n인 11111.....1111000011...과 같은 문자열이 있을 때, 길이가 n-e인 부분문자열은  처음 연속하는 1의 길이가 4이하인 것이 가장 좋다.

 

그리고 여기서 정답으로 도달하는 마지막 관찰!

 

위 조건을 만족하는 문자열은 단 한개 뿐이다.

 

가장 처음 시작하는 0을 1로 만들기 위한 길이를 만족하면서, 1이 중간에 끊기는 부분 문자열은 s-e지점에서 l만큼의 길이 이전에 시작하는 부분 문자열이 유일하다.

 

몇가지 예외케이스가 존재하기에 이들만 처리해주면 끝.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
	
	int t;
	cin >> t;
	while(t--) {
		int n, s = -1, e = -1, zeroend;
		string s1, s2;
		s2 = "";
		cin >> n >> s1;
		zeroend = n;
		for(int i = 0; i < n; i++) {
			if(s1[i] == '1') {
				s = i;
				break;
			}
		}
		if(s == -1) {
			cout << "0\n";
			continue;
		}
		for(int i = s; i < n; i++) {
			if(s1[i] == '0') {
				e = i;
				break;
			}
		}
		if(e == -1) {
			if(s == 0) {
				for(int i = 0; i < n-1; i++) {
					cout << s1[i];
				}
				cout << "0\n";
			}
			else {
				for(int i = s; i < n; i++) {
					cout << s1[i];
				}
				cout << "\n";
			}
			continue;
		}
		for(int i = e; i < n; i++) {
			if(s1[i] == '1') {
				zeroend = i;
				break;
			}
		}
		int l = zeroend - e, tl = n-e;
		for(int i = max(s, e-l); i < max(s, e-l)+tl; i++) {
			s2 += s1[i];
		}

		for(int i = s; i < e; i++) {
			cout << s1[i];
		}
		for(int i = e; i < n; i++) {
			cout << abs(s1[i] - s2[i-e]);
		}
		cout << "\n";

	}
}